051.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
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;
}