Sieve of Eratosthenes
bool isPrime[MAXN];
void sieve_of_Eratosthenes(int n) {
isPrime[0] = isPrime[1] = true;
for (int i = 2; i <= n; ++i)
if (!isPrime[i])
for (int j = i << 1; j <= n; j += i)
isPrime[j] = true;
}
Sieve of Euler
int prime[MAXN];
bool isPrime[MAXN];
void sieve_of_Euler(int n) {
isPrime[0] = isPrime[1] = true;
int pNum = 0;
int upto = n >> 1 | 1;
for (int i = 2; i <= upto; ++i) {
if (!isPrime[i])
prime[++pNum] = i;
for (int j = 1; j <= pNum && prime[j] * i <= n; ++j) {
isPrime[prime[j] * i] = true;
if (!(i % prime[j]))
break;
}
}
}
*Sieve of Sundaram
#include <cstdio>
const int MAXN = 10000010;
bool isPrime[MAXN];
void sieve_of_Sundaram(int n) {
isPrime[0] = true;
for (int i = 1; i <= n; ++i) {
int upto = (n - i) / (i << 1 | 1);
for (int j = 1; j <= upto; ++j)
isPrime[i + j + (i * j << 1)] = 1;
}
}
int main() {
int n;
scanf("%d", &n);
sieve_of_Sundaram(n);
for (int i = 2; i <= n; ++i) {
if (i & 1 && !isPrime[i >> 1])
printf("%d ", i);
}
}
Source Code: github
Top comments (0)