結果

問題 No.1657 Sum is Prime (Easy Version)
ユーザー 杨娵隅
提出日時 2021-08-27 23:17:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 895 ms / 2,000 ms
コード長 1,962 bytes
コンパイル時間 2,279 ms
コンパイル使用メモリ 190,668 KB
最終ジャッジ日時 2025-01-24 03:38:54
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

//code of JUYU ^ ^ never doubt youself !
#include <bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;++i)
#define Dow(i,j,k) for(int i=k;i>=j;--i)
#define ms(a,b) memset(a,b,sizeof a)
#define ll long long
#define pa pair<int,int>
#define fir first
#define sec second
#define eb emplace_back
#define pb push_back
#define mk make_pair

using namespace std;

const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

int ans;  //exactly you can get the answer

inline ll read()
{
  ll t = 0, dp = 1; char c = getchar();
  while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
  return t * dp;
}
inline void write(ll x){if (x < 0)  {putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}

int prime[N], cnt;
bool st[N];

void get_prime(int x) 
{
  for (int i = 2; i <= x; i ++) 
  {
    if (!st[i]) prime[cnt ++] = i;
    for (int j = 0; prime[j] <= x / i; j ++) 
    {
      //对于任意一个合数x，假设pj为x最小质因子，当i<x/pj时，一定会被筛掉
      st[prime[j] * i] = true;
      if(i % prime[j] == 0) break;
      /*
      1.i%pj == 0, pj定为i最小质因子，pj也定为pj*i最小质因子
      2.i%pj != 0, pj定小于i的所有质因子，所以pj也为pj*i最小质因子
      */
    }
  }
}

bool isprime(int x)
{
  if (x < 2) return false;

  for (int i = 2; i <= x / i; i ++)
  {
    if (x % i == 0) return false;
  }return true;
}

signed main()
{
  
  int l = read(), r = read();
  
  int ans = 0;
  For(i,l,r)
  {
    if (isprime(i)) ans ++;
    if (isprime(i * 2 + 1) && i != r) ans ++;
  }
  
  writeln(ans);
  
  return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 -- Benq
*/
0