From 235aef5fae393c738e78a5b188051557b6ebd97c Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Mon, 16 Apr 2018 21:15:33 +0800
Subject: 1.6

---
 1.6/sprime.c | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 112 insertions(+)
 create mode 100644 1.6/sprime.c

(limited to '1.6/sprime.c')

diff --git a/1.6/sprime.c b/1.6/sprime.c
new file mode 100644
index 0000000..4611c33
--- /dev/null
+++ b/1.6/sprime.c
@@ -0,0 +1,112 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: sprime
+*/
+
+#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;
+}
+
+static int isprime(int n) { return miller_rabin(n)==1; }
+
+FILE *fin, *fout;
+
+void search_sprime(int N, int s)
+{
+	int i;
+
+	if (N == 0) {
+		fprintf(fout, "%d\n", s);
+		return;
+	}
+
+	if (s == 0) {
+		search_sprime(N-1, 2);
+	}
+	for (i=1; i<=9; i+=2) {
+		if (isprime(s*10+i))
+			search_sprime(N-1, s*10+i);
+	}
+}
+
+
+int main()
+{
+	int N;
+
+	fin = fopen("sprime.in", "r");
+	fout = fopen("sprime.out", "w");
+
+	fscanf(fin, "%d", &N);
+	fclose(fin);
+
+	search_sprime(N, 0);
+	fclose(fout);
+	return 0;
+}
-- 
cgit v1.2.3