const int N_MAX = 10010;
bool is_prime[N_MAX];
void Eratosthenes(){
FOR(i, 0, N_MAX){
is_prime[i] = true;
}
is_prime[0] = false;
is_prime[1] = false;
FOR(i, 2, N_MAX){
if(is_prime[i]==1){
int p = i;
int step_p = p;
while(p < N_MAX){
p += step_p;
if(p<N_MAX){
is_prime[p] = 0;
}
}
}
}
}
- 再利用しやすく書いたので保存
- ちなみにこちらの問題で使った
- N=10000のとき1200ほど
- N=100000のとき9500ほど
- ということで10%くらいで見ておけばいい
今回の問題の計算量
- N = 10000
- それぞれに対して素数リストでforをするので、
- 計算量は10000 x 1000 = 107
- よって間に合う
どこまで作れる?
- 素数20万個なら制限時間内で作れる
- その時にforで回す整数は270万ほど
const int M = 2750131;
int P[200000];
int invP[M + 1];
int minP[M + 1];
bool isP[M + 1];
void Eratosthenes() {
int p = 0;
REP(i, M + 1) isP[i] = true, minP[i] = -1;
isP[0] = isP[1] = false;
minP[0] = 0; minP[1] = 1;
FOR(i, 2, M + 1) {
if (isP[i]) {
minP[i] = i;
P[p] = i;
invP[i] = p++;
for (int j = i * 2; j < M; j += i) {
isP[j] = false;
if (minP[j] == -1) minP[j] = i;
}
}
}
}