Generates all prime numbers less than 1000000 using the Sieve of Eratosthenes.

sieve.c

#include <stdlib.h>

/*
 * returns an int[] where int[0] is the length of the array
 * and subsequent elements are the primes themselves.
 */
int* findprimes(int range) {
	int prime = 2;
	int i;
	int *notprime = calloc(sizeof(notprime), range);
	
	notprime[0] = notprime[1] = 1;
	while (prime * prime < range) {
		for (i = 2; i * prime < range; i++)
			notprime[i * prime] = 1;
		while (notprime[++prime])
			;
	}
	
	prime = 0;
	for (i = 0; i < range; i++) {
		if (!notprime[i])
			prime++;
	}
	
	notprime[0] = prime + 1;
	prime = 1;// prime now acts as a ptr for unfilled space
	for (i = 1; i < range; i++) {
		if (!notprime[i]) {
			notprime[prime++] = i;
		}
	}
	
	return notprime;
}

~main.c

#include <stdio.h>

int main() {
	int i;
	int *a = findprimes(1000000);
	for (i = 1; i < a[0]; i++)
		printf("%d\n", a[i]);
	return 0;
}