From 7f25c6fc31b376ca1ed0f4c183ef4d232b6ee2b5 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Sun, 3 Jun 2018 21:49:08 +0800
Subject: 73,74,85,357

---
 euler357.c | 117 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 117 insertions(+)
 create mode 100644 euler357.c

(limited to 'euler357.c')

diff --git a/euler357.c b/euler357.c
new file mode 100644
index 0000000..bee6d95
--- /dev/null
+++ b/euler357.c
@@ -0,0 +1,117 @@
+#include <stdio.h>
+
+/* Time: 2m5.335s */
+
+typedef struct
+{
+	int p;
+	int np;
+} prime_factor;
+
+/* factorize n, return number of prime factors */
+int get_prime_factors(int n, prime_factor *pf)
+{
+	int npf = 0;
+	int np;
+	if (n <= 1)
+		return 0;
+	if (n % 2 == 0) {
+		pf[0].p = 2;
+		np = 0;
+		while (n % 2 == 0) {
+			n /= 2;
+			np++;
+		}
+		pf[0].np = np;
+		npf = 1;
+	}
+	for (int i = 3; i * i <= n; i += 2) {
+		if (n % i == 0) {
+			pf[npf].p = i;
+			np = 0;
+			while (n % i == 0) {
+				n /= i;
+				np ++;
+			}
+			pf[npf].np = np;
+			npf++;
+		}
+	}
+	if (n > 1) {
+		pf[npf].p = n;
+		pf[npf].np = 1;
+		npf++;
+	}
+	return npf;
+}
+
+int get_factors_from_pf(prime_factor pf[], int npf, int factors[])
+{
+	factors[0] = 1;
+	int idx = 1;
+	for (int i = 0; i < npf; i++) {
+		int nidx = idx;
+		for (int j = 0; j < pf[i].np; j++) {
+			for (int k = 0; k < idx; k++) {
+				factors[nidx+k] = factors[nidx+k-idx] * pf[i].p;
+			}
+			nidx += idx;
+		}
+		idx = nidx;
+	}
+	return idx;
+}
+
+int get_all_factors(int n, int factors[])
+{
+	prime_factor pf[100];
+	int npf = get_prime_factors(n, pf);
+
+	return get_factors_from_pf(pf, npf, factors);
+}
+
+int isprime(int n)
+{
+	if (n < 2 || n % 2 == 0)
+		return 0;
+
+	for (int i = 3; i * i <= n; i += 2) {
+		if (n % i == 0)
+			return 0;
+	}
+
+	return 1;
+}
+
+int main()
+{
+	long long sum = 3; /* n can be 1, 2 */
+	int factors[10000];
+	prime_factor pf[100];
+
+	for (int i = 6; i <= 100000000; i += 4) { /* n must be 4k+2 */
+		int isok = 1;
+		int npf = get_prime_factors(i, pf);
+		for (int j = 0; j < npf; j++) {
+			if (pf[j].np > 1) {
+				isok = 0;
+				break;
+			}
+		}
+		if (!isok)
+			continue;
+
+		int nf = get_factors_from_pf(pf, npf, factors);
+		for (int j = 0; j < nf; j++) {
+			int t = factors[j] + i/factors[j];
+			if (!isprime(t)) {
+				isok = 0;
+				break;
+			}
+		}
+		if (isok) {
+			sum += i;
+		}
+	}
+	printf("%lld\n", sum);
+}
-- 
cgit v1.2.3