DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world
Generate Prime Numbers
GenPrime(int n) generates all prime numbers smaller or equal to n, storing them in prime[]. NrPrime is the number of prime numbers calculated.
This uses the "Primes Sieve of Eratosthenes".
#include <string.h>
int prime[78498]; // 78498 is the number of prime numbers smaller than 1 000 000.
int nrPrime = 0;
void genPrime(int n) {
char p[1000001];
memset(p, 1, sizeof(char) * (n + 1));
p[1] = 0;
int i = 2;
for (; i <= n; ++i)
if (p[i]) {
prime[nrPrime] = i;
++nrPrime;
int j = i * 2;
while (j <= n) {
p[j] = 0;
j += i;
}
}
}
