This is something I use quite a bit for various problems and programming exercises, so I figured I could post it here. It’s a basic post that isn’t advanced at all, but that doesn’t mean that the implementation given below won’t save work for others. The idea is to create a list of primes in C by malloc’ing a sieve, then malloc’ing a list of specific length based on that sieve. The resulting list contains all the primes below a given limit (defined in the code). The first member of the list is an integer representing the length of the list.

#include <stdio.h> #include <stdlib.h> #include <malloc.h> #define bool _Bool static unsigned long prime_limit = 1000000; unsigned long sqrtld(unsigned long N) { int b = 1; unsigned long res,s; while(1<<b<N) b+= 1; res = 1<<(b/2 + 1); for(;;) { s = (N/res + res)/2; if(s>=res) return res; res = s; } } unsigned long * make_primes(unsigned long limit) { unsigned long *primes; unsigned long i,j; unsigned long s = sqrtld(prime_limit); unsigned long n = 0; bool *sieve = malloc((prime_limit + 1) * sizeof(bool)); sieve[0] = 0; sieve[1] = 0; for(i=2; i<=prime_limit; i++) sieve[i] = 1; j = 4; while(j<=prime_limit) { sieve[j] = 0; j += 2; } for(i=3; i<=s; i+=2) { if(sieve[i] == 1) { j = i * 3; while(j<=prime_limit) { sieve[j] = 0; j += 2 * i; } } } for(i=2;i<=prime_limit;i++) if(sieve[i]==1) n += 1; primes = malloc((n + 1) * sizeof(unsigned long)); primes[0] = n; j = 1; for(i=2;i<=prime_limit;i++) if(sieve[i]==1) { primes[j] = i; j++; } free(sieve); return primes; } int main(void) { unsigned long * primes = make_primes(prime_limit); printf("There are %ld primes <= %ld\n",primes[0],prime_limit); free(primes); return 0; }

Say one wanted to form a list of all primes below 1,000,000. That’s what the above program does by default, since “prime_limit = 1000000.” If one compiles this and executes, you would get something like what follows. The timing is relatively respectable.

$ gcc -O3 -o prime-sieve prime-sieve.c $ time ./prime-sieve There are 78498 primes <= 1000000 real 0m0.008s user 0m0.004s sys 0m0.000s

The code is linked here: prime-sieve.c