From 8b5700048e51297ffdd160b6f743ff02a0418c85 Mon Sep 17 00:00:00 2001
From: Reiner Herrmann <reiner@reiner-h.de>
Date: Sat, 3 Dec 2011 19:25:57 +0100
Subject: projecteuler: alternate solution for 69; solution for 80

---
 src/projecteuler/069_2.py | 22 +++++++++++++++++++
 src/projecteuler/080.py   | 55 +++++++++++++++++++++++++++++++++++++++++++++++
 src/projecteuler/common.c |  1 +
 3 files changed, 78 insertions(+)
 create mode 100644 src/projecteuler/069_2.py
 create mode 100644 src/projecteuler/080.py

diff --git a/src/projecteuler/069_2.py b/src/projecteuler/069_2.py
new file mode 100644
index 0000000..c00483b
--- /dev/null
+++ b/src/projecteuler/069_2.py
@@ -0,0 +1,22 @@
+#
+# n/phi(n) is a maximum, if phi(n) is minimal
+#
+# phi(n) = n*(1-1/p1)*(1-1/p2)*...*(1-1/pi)
+# n/phi(n) = 1/((1-1/p1)*(1-1/p2)*...*(1-1/pi))
+# -> smallest primes
+#
+
+from common import sieve
+
+primes = sieve(100).primes()
+prime_list = [ x for x in primes ]
+prime_list.sort()
+
+x = 1
+for p in prime_list:
+    if x*p > 1000000:
+	break
+    x *= p
+
+print x
+
diff --git a/src/projecteuler/080.py b/src/projecteuler/080.py
new file mode 100644
index 0000000..9becd19
--- /dev/null
+++ b/src/projecteuler/080.py
@@ -0,0 +1,55 @@
+
+# schriftliches wurzelziehen: http://www.diaware.de/html/wurzel.html
+
+def sqrt(x, accuracy):
+    a = [] # vor komma
+    b = [] # nach komma
+
+    groups = []
+    while x > 0:
+	groups.append(x % 100)
+	x /= 100
+    groups = groups[::-1]
+
+    result = 0
+    remainder = 0
+    while accuracy > 0:
+	group = 100 * remainder
+	if len(groups) > 0:
+	    group += groups[0]
+
+	subcount = 0
+	sub = 20*result + 1
+	while sub < group:
+	    group -= sub
+	    if group < 0:
+		break
+	    subcount += 1
+	    sub += 2
+	    remainder = group
+	if subcount == 0:
+	    remainder *= 100
+	result *= 10
+	result += subcount
+
+	if len(groups) > 0:
+	    a.append(subcount)
+	    del groups[0]
+	else:
+	    b.append(subcount)
+	accuracy -= 1
+
+    return (a, b)
+
+squares = set([ x*x for x in range(11) ])
+
+digitsum = 0
+
+for n in xrange(100):
+    if n in squares:
+	continue
+    s = sqrt(n, 100)
+    digitsum += sum(s[0]) + sum(s[1])
+
+print digitsum
+
diff --git a/src/projecteuler/common.c b/src/projecteuler/common.c
index 52e5173..69f87c5 100644
--- a/src/projecteuler/common.c
+++ b/src/projecteuler/common.c
@@ -1,6 +1,7 @@
 #include <stdlib.h>
 #include <string.h>
 
+// returns list of primes up to limit; count stored in first element
 extern unsigned long* primes(unsigned long limit)
 {
 	unsigned long i = 2; // start sieving with 2
-- 
cgit v1.2.3