/*
	Low resource-using, yet fast primenumber generator.
	Uses a partial table, and can be made 're-entrant', which can save time and memory.

	Algorithm by Kalms and X-Calibre, copyright 2000

	Coded by X-Calibre
 */

#include <stdio.h>

#define ARRAYSIZE	16384		/* the temporary ('partial') table size. experiment and find the ideal table/span ratio */
#define	SPAN		1000000		/* generate primes from 0 to SPAN (note that SPAN is rounded up, due to the nature of the algorithm) */

unsigned long int primes[ARRAYSIZE], i, j, k, l, nrOfPrimes = 1, *primeList, listSize = ARRAYSIZE, arrayBase = ARRAYSIZE;

int main()
{
	/* clear all bools */
	memset(primes, 0, ARRAYSIZE << 2);

	/* allocate memory for list of found primes */
	primeList = (unsigned long *)malloc(ARRAYSIZE << 2);
	
	/* mark 2, as only prime that is not being checked */
	primeList[0] = 2;

	printf("2\n");

	for (k = 3; k < (ARRAYSIZE << 6); k += 2)
	{
		if ( (primes[k >> 6] & (1 << ((k >> 1) & 0x1F))) == 0)	/* prime */
		{
			primeList[nrOfPrimes] = k;	/* add found prime to list */
			
			printf("%u\n", k);

			/* If list is full, grow the array */
			if(++nrOfPrimes >= listSize)
			{
				if(!(primeList = (unsigned long *)realloc(primeList, (listSize+=listSize) << 2)))
				{
					printf("Ran out of memory while trying to expand list of found prime numbers.\n");
					break;
				}
			}

			for (j = k + k; j < (ARRAYSIZE << 6); j += k)
			{
				if (j & 1)
					primes[j >> 6] |= (1 << ((j >> 1) & 0x1F));	/* mark as non-prime */
			}
		}
	}

	while(k < SPAN)
	{
		printf("\nReset table at: %u\n\n", k);

		/* clear all bools again */
		memset(primes, 0, ARRAYSIZE << 2);

		/* reinstate already found primes in part of table */
		for (l = 1; l < nrOfPrimes; l++)
		{
			i = primeList[l];

			for (j = i - ((arrayBase << 6) % i); j < (ARRAYSIZE << 6); j += i)
				if (j & 1)
					primes[j >> 6] |= (1 << ((j >> 1) & 0x1F));	/* mark as non-prime */
		}

		/* continue searching for primes */
		for (; k <= (((arrayBase << 6)-1) + (ARRAYSIZE << 6)); k += 2)
		{
			i = k - (arrayBase << 6);
			
			if ( (primes[i >> 6] & (1 << ((i >> 1) & 0x1F))) == 0)	/* prime */
			{
				primeList[nrOfPrimes] = k;	/* add found prime to list */

				printf("%u\n", k);

				/* If list is full, grow the array */
				if(++nrOfPrimes >= listSize)
				{
					if(!(primeList = (unsigned long *)realloc(primeList, (listSize+=listSize) << 2)))
					{
						printf("Ran out of memory while trying to expand list of found prime numbers.\n");
						goto endSearch;
					}
				}

				for (j = i - ((arrayBase << 6) % i); j < (ARRAYSIZE << 6); j += k)
					if (j & 1)
						primes[j >> 6] |= (1 << ((j >> 1) & 0x1F));	/* mark as non-prime */
			}
		}

		arrayBase += ARRAYSIZE;
	}

endSearch:
	printf("Searched up to: %u\nTotal primes found: %u\n\n", k, nrOfPrimes);

	return 0;
}