1 files changed, 124 insertions, 0 deletions
diff --git a/1.6/pprime.c b/1.6/pprime.c
new file mode 100644
index 0000000..57d930e
--- /dev/null
+++ b/1.6/pprime.c
@@ -0,0 +1,124 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: pprime
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+static int sqrmod(int b, int n)
+{
+	long long t = b;
+	t *= t;
+	return t % n;
+}
+
+int expmod(int b, int e, int n)
+{
+	long long t;
+	if (e == 0)
+		return 1;
+
+	t = expmod(b, e/2, n);
+	t = sqrmod(t, n);
+	if (e%2) {
+		t *= b;
+		t %= n;
+	}
+
+	return t;
+}
+
+int mr_test(int test, int n)
+{
+	int s, r;
+	long long t;
+	r = 0;
+	for (s = n-1; s%2==0; s/=2)
+		r++;
+	t = expmod(test, s, n);
+	if (t==1)
+		return 1;
+	while (r--) {
+		if (t==n-1)
+			return 1;
+		t = sqrmod(t, n);
+	}
+	return 0;
+}
+
+/* Miller-Rabin test:
+ * return 1 if considered prime,
+ * otherwise return the proof of non-prime
+ */
+int miller_rabin(const int n)
+{
+	int r;
+	int i;
+
+	if (n==2 || n==3 || n==5 || n==7)
+		return 1;
+
+	if (n%2==0 || n==1)
+		return 0;
+
+	for (i=0; i<100; i++) {
+		do {
+			r = rand() % n;
+		} while (r==0 || r==1 || r==n-1);
+		if (!mr_test(r, n))
+			return r;
+	}
+	return 1;
+}
+
+int make_palindrome(int half, int odd)
+{
+	int s = half;
+	int r = (odd)?half/10:half;
+	while (r) {
+		s = s*10+(r%10);
+		r /= 10;
+	}
+	return s;
+}
+
+int main()
+{
+	FILE *fin, *fout;
+	int a, b;
+	int i,j;
+	int base, base_max;
+	int stopped = 0;
+
+	fin = fopen("pprime.in", "r");
+	fout = fopen("pprime.out", "w");
+
+	fscanf(fin, "%d%d", &a, &b);
+
+	for (base=1; make_palindrome(base, 1)<a; base*=10)
+		;
+	base /= 10;
+
+	while (!stopped) {
+		base_max = base*10-1;
+		for (j=1; j>=0; j--) {
+			for (i=base; i<=base_max; i++) {
+				int t = make_palindrome(i, j);
+				if (t<a)
+					continue;
+				if (t>b) {
+					stopped = 1;
+					break;
+				}
+				if (miller_rabin(t) == 1)
+					fprintf(fout, "%d\n", t);
+			}
+		}
+		base *= 10;
+	}
+
+	fclose(fout);
+	return 0;
+}