73,74,85,357

4 files changed, 229 insertions, 0 deletions

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);
+}
diff --git a/euler73.c b/euler73.c
new file mode 100644
index 0000000..ea146b2
--- /dev/null
+++ b/euler73.c
@@ -0,0 +1,23 @@
+#include <stdio.h>
+
+int gcd(int a, int b)
+{
+	if (a==0)
+		return b;
+	else
+		return gcd(b%a, a);
+}
+
+int main()
+{
+	int count = 0;
+	for (int d = 5; d <= 12000; d++) {
+		int lo = d/3+1;
+		int hi = d/2;
+		for (int i = lo; i <= hi; i++) {
+			if (gcd(i, d)==1)
+				count++;
+		}
+	}
+	printf("%d\n", count);
+}
diff --git a/euler74.c b/euler74.c
new file mode 100644
index 0000000..a0020f6
--- /dev/null
+++ b/euler74.c
@@ -0,0 +1,57 @@
+#include <stdio.h>
+#include <string.h>
+
+#define MAXTERM 3000000
+int next[MAXTERM];
+
+const int factorial[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
+
+int sum_fact_digits(int n)
+{
+	int sum = 0;
+	while (n > 0) {
+		sum += factorial[n%10];
+		n /= 10;
+	}
+	return sum;
+}
+
+void init()
+{
+	memset(next, 0, sizeof(next));
+	for (int i = 1; i < 1000000; i++) {
+		if (next[i])
+			continue;
+		next[i] = sum_fact_digits(i);
+		for (int j = next[i]; next[j] == 0; j = next[j]) {
+			next[j] = sum_fact_digits(j);
+		}
+	}
+}
+
+int chainlen(int n)
+{
+	int chain[100], L = 0;
+
+	while (1) {
+		for (int i = 0; i < L; i++) {
+			if (chain[i] == n)
+				return L;
+		}
+		chain[L] = n;
+		L++;
+		n = next[n];
+	}
+}
+
+int main()
+{
+	int count = 0;
+
+	init();
+	for (int i = 1; i <= 1000000; i++) {
+		if (chainlen(i) == 60)
+			count++;
+	}
+	printf("%d\n", count);
+}
diff --git a/euler85.c b/euler85.c
new file mode 100644
index 0000000..97687bb
--- /dev/null
+++ b/euler85.c
@@ -0,0 +1,32 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+/* rectangle count for a m*n grid:
+ * for i = 1 to m
+ *   for j = 1 to n
+ *     (m-i+1)*(n-j+1)
+ * = [m(m+1)/2][n(n+1)/2]
+ */
+
+#define AREA 2000000
+
+int main()
+{
+	int m, n, bestm, bestn;
+	int nearest = AREA;
+	for (m = 1; m <= 2000; m++) {
+		int a1 = m*(m+1)/2;
+		for (n = 1; n <= 2000; n++) {
+			int area = a1*n*(n+1)/2;
+			if (area > AREA && area-AREA>nearest)
+				break;
+			if (abs(area-AREA) < nearest) {
+				nearest = abs(area-AREA);
+				bestm = m;
+				bestn = n;
+			}
+		}
+	}
+
+	printf("%d * %d = %d\n", bestm, bestn, bestm*bestn);
+}