#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;
}