From f7c10015f1077ea4e3d97537a8c15e79bbb6b5e6 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Thu, 28 Jun 2018 10:49:35 +0800
Subject: 51

---
 euler51.c | 113 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 113 insertions(+)
 create mode 100644 euler51.c

diff --git a/euler51.c b/euler51.c
new file mode 100644
index 0000000..dd13881
--- /dev/null
+++ b/euler51.c
@@ -0,0 +1,113 @@
+#include <stdio.h>
+
+#define MAXLEN 20
+
+unsigned long long p10[MAXLEN];
+
+#define MAXNUM 100000000
+int nprimes;
+int primes[MAXNUM];
+
+void getprimes()
+{
+	primes[0] = 2;
+	nprimes = 1;
+	for (int i = 3; i <= MAXNUM; i+=2) {
+		int isprime = 1;
+		for (int j = 0; j < nprimes; j++) {
+			if (primes[j] * primes[j] > i)
+				break;
+			if (i % primes[j] == 0) {
+				isprime = 0;
+				break;
+			}
+		}
+		if (isprime) {
+			primes[nprimes] = i;
+			nprimes ++;
+		}
+	}
+}
+
+void init()
+{
+	int i;
+
+	p10[0] = 1;
+	for (i = 1; i < MAXLEN; i++)
+		p10[i] = p10[i-1] * 10;
+	getprimes();
+}
+
+int isprime(unsigned long long x)
+{
+	for (int i = 0; primes[i] * primes[i] <= x; i++) {
+		if (x % primes[i] == 0)
+			return 0;
+	}
+	return 1;
+}
+
+static int getdigits(unsigned long long x, int d[])
+{
+	int nd = 0;
+	while (x > 0) {
+		d[nd] = x % 10;
+		nd++;
+		x /= 10;
+	}
+	return nd;
+}
+
+/* the number of digits to be replaced must be multiple of 3,
+ * otherwise at least 3 of the replaced numbers are multiple of 3
+ */
+int search3(unsigned long long x)
+{
+	int digits[40];
+	int nd;
+	int i, j, k;
+	unsigned long long t;
+
+	nd = getdigits(x, digits);
+
+	for (i = 0; i < nd-2; i++) {
+		if (digits[i] >= 3) /* at most 7 numbers */
+			continue;
+		for (j = i+1; j < nd-1; j++) {
+			if (digits[j] != digits[i])
+				continue;
+			for (k = j+1; k < nd; k++) {
+				if (digits[k] != digits[i])
+					continue;
+				unsigned long long delta = p10[i] + p10[j] + p10[k];
+				int cnt = 1; /* assume x is prime */
+				t = x;
+				int tmp = digits[i] + 1;
+				while (tmp < 10) {
+					t += delta;
+					if (isprime(t))
+						cnt++;
+
+					tmp++;
+				}
+				if (cnt >= 8)
+					return 1;
+			}
+		}
+	}
+	return 0;
+}
+
+int main()
+{
+	unsigned long long t = 1001;
+	init();
+	while (1) {
+		if (isprime(t) && search3(t)) {
+			printf("%lld\n", t);
+			return 0;
+		}
+		t += 2;
+	}
+}
-- 
cgit v1.2.3