Prime Sieve Algorithm Cheat Sheet

#algorithms #mathematics

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);
  }
}