Written by razrlele
21:09 December 6, 2014
|
1 2 3 |
const int maxn = 1000000; int primenum; bool visit[maxn]; |
常规素数打表
时间复杂度为n^2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
void init_prime() { memset(visit, false, sizeof(visit)); for(int i = 2; i < sqrt(maxn+2); i++) { if(!visit[i]) for(j = i*i; j < (maxn+2); j += i) { visit[j] = true; } } primenum = 0; for(int i = 2; i <= (maxn+2); i++) { if(!visit[i]) prime[primenum++] = i; } return ; } |
线性时间素数打表
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void init_prime() { memset(visit, false, sizeof(visit)); for(int i = 2; i <= maxn; i++) { if(!visit[i]) { prime[primenum++] = i; } for(int j = 0; j < primenum && i*prime[j] <= maxn; j++) { visit[i*prime[j]] = true; if(i%prime[j] == 0) break; } } } |