projecteuler solution 051

1 files changed, 121 insertions, 0 deletions

diff --git a/src/projecteuler/051.c b/src/projecteuler/051.c
new file mode 100644
index 0000000..ee79ece
--- /dev/null
+++ b/src/projecteuler/051.c
@@ -0,0 +1,121 @@
+#include "common.h"
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+unsigned long* p;
+
+const int pattern_size = 1024;
+unsigned long* patterns;
+
+void init_patterns()
+{
+	int i, cur;
+	unsigned long n, pos;
+
+	patterns = (unsigned long*) malloc(pattern_size*sizeof(unsigned long));
+
+	for(i=0; i<pattern_size; i++)
+	{
+		pos = 1;
+		cur = i;
+		n = 0;
+		while(cur > 0)
+		{
+			n += (cur&1)*pos;
+			pos *= 10;
+			cur >>= 1;
+		}
+		patterns[i] = n;
+	}
+}
+
+int valid_replacement(unsigned long prime, unsigned long number, unsigned long pattern)
+{
+	int digit = -1; // replaced digit in prime
+
+	while(pattern > 0)
+	{
+		char d1 = pattern % 10;
+		char d2 = prime % 10;
+		char d3 = number % 10;
+
+		if(d1 == 1)
+		{
+			if(digit < 0)
+				digit = d2;
+			else if(digit != d2) // not same digits replaced
+				return 0;
+		}
+
+		if(d1 == 0 && d2 != d3)
+			return 0;
+		else if(prime == 0 && number != 0)
+			return 0;
+
+		pattern /= 10;
+		prime /= 10;
+		number /= 10;
+	}
+
+	if(pattern == 0 && prime != number)
+		return 0;
+
+	return 1;
+}
+
+int check_prime(unsigned long prime)
+{
+	int i, j;
+
+	for(i=2; i<pattern_size; i++)
+	{
+		unsigned long pat = patterns[i];
+		unsigned long tmp = prime;
+		int count = 1;
+
+		if(pat >= 10*tmp)
+			break;
+
+		for(j=0; j<10; j++)
+		{
+			tmp += pat;
+
+			if(isprime(tmp, p) && valid_replacement(prime, tmp, pat))
+				count++;
+		}
+
+		if(count>=8)
+		{
+			printf("Pattern: %ld\n", pat);
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
+int main(void)
+{
+	unsigned long pcount;
+	unsigned long pos;
+
+	p = primes(1000000);
+	pcount = p[0];
+
+	init_patterns();
+
+	for(pos=1; pos<=pcount; pos++)
+	{
+		if(check_prime(p[pos]))
+		{
+			printf("Prime: %li\n", p[pos]);
+			break;
+		}
+	}
+
+	free(p);
+	free(patterns);
+	return 0;
+}
+