結果
問題 |
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 |
ソースコード
//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 */