1 files changed, 107 insertions, 0 deletions
diff --git a/src/projecteuler/common.c b/src/projecteuler/common.c
new file mode 100644
index 0000000..15ac8aa
--- /dev/null
+++ b/src/projecteuler/common.c
@@ -0,0 +1,107 @@
+#include <stdlib.h>
+#include <string.h>
+
+extern unsigned long* primes(unsigned long limit)
+{
+	unsigned long i = 2; // start sieving with 2
+	unsigned long pos, x;
+	char* numbers = (char*) malloc(limit*sizeof(char));
+	unsigned long* primes;
+	unsigned long primecount = 0;
+	memset(numbers, 1, limit);
+	numbers[0] = 0;
+
+	while(i*i <= limit)
+	{
+		// sieve current prime
+		x = i*i;
+		while(x <= limit)
+		{
+			numbers[x-1] = 0;
+			x += i;
+		}
+		
+		// search next prime
+		pos = i;
+		while(++pos <= limit)
+		{
+			if(numbers[pos-1] == 1)
+				break;
+		}
+		i = pos;
+	}
+
+	// count primes
+	pos = 0;
+	while(++pos <= limit)
+	{
+		if(numbers[pos-1] == 1)
+			primecount++;
+	}
+
+	// create list of primes
+	primes = (unsigned long*) malloc((primecount+1)*sizeof(unsigned long)); // store count at first element
+	primes[0] = primecount;
+	pos = 0;
+	x = 1;
+	while(++pos <= limit)
+	{
+		if(numbers[pos-1] == 1)
+			primes[x++] = pos;
+	}
+
+	free(numbers);
+	return primes;
+}
+
+extern int isprime(unsigned long number, const unsigned long* primes)
+{
+	unsigned long count = primes[0];
+	unsigned long pos = count/2 + 1;
+	unsigned long dist = pos/2 + 1;
+	unsigned long minpos = 0, maxpos = count;
+
+	if(number > primes[count] || number < 2)
+		return 0;
+
+	// some kind of binary search...
+	while(1)
+	{
+		if(number > primes[pos])
+		{
+			minpos = pos;
+			pos += dist;
+		}
+		else if(number < primes[pos])
+		{
+			maxpos = pos;
+			pos -= dist;
+		}
+		else
+			return 1;
+
+		dist /= 2;
+
+		if(dist == 1)
+		{
+			while(++minpos <= maxpos)
+				if(primes[minpos] == number)
+					return 1;
+			break;
+		}
+	}
+
+	return 0;
+}
+
+/*int main()
+{
+	long* p = primes(10000);
+	//printf("%i\n", isprime(9973, p));
+	int i;
+	for(i=0; i<p[0]; i++)
+		printf("%d: %d\n", p[i+1], isprime(p[i+1], p));
+	free(p);
+	return 0;
+}*/
+