#693389 (C++17) No.1657 Sum is Prime (Easy Version)

• 問題: No.1657 Sum is Prime (Easy Version)
• ユーザー: 杨娵隅
• 提出日時: 2021-08-27 23:17:27
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 767 ms / 2,000 ms
• コード長: 1,962 bytes
• コンパイル時間: 1,922 ms
• コンパイル使用メモリ: 200,500 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-21 05:13:44
• 合計ジャッジ時間: 6,861 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	688 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	3 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	3 ms; 5,248 KB
testcase_12	AC	640 ms; 5,248 KB
testcase_13	AC	230 ms; 5,248 KB
testcase_14	AC	321 ms; 5,248 KB
testcase_15	AC	417 ms; 5,248 KB
testcase_16	AC	96 ms; 5,248 KB
testcase_17	AC	19 ms; 5,248 KB
testcase_18	AC	48 ms; 5,248 KB
testcase_19	AC	638 ms; 5,248 KB
testcase_20	AC	171 ms; 5,248 KB
testcase_21	AC	767 ms; 5,248 KB
testcase_22	AC	2 ms; 5,248 KB
testcase_23	AC	86 ms; 5,248 KB

ソースコード

//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
*/