project euler solution #37

1 files changed, 61 insertions, 0 deletions

diff --git a/src/projecteuler/037.py b/src/projecteuler/037.py
new file mode 100644
index 0000000..5e506c2
--- /dev/null
+++ b/src/projecteuler/037.py
@@ -0,0 +1,61 @@
+
+limit = 800000
+
+number_list = [False] + [True]*(limit-1)
+list_len = len(number_list)
+
+def next_prime(i):
+	global number_list
+	global list_len
+	x = i+1
+	while(x <= list_len):
+		if number_list[x-1] == True:
+			break
+		x += 1
+	return x
+
+i = 2
+
+while(i*i <= list_len):
+	x = i*i
+	while(x <= list_len):
+		number_list[x-1] = False
+		x += i
+	i = next_prime(i)
+
+
+primes = set()
+
+for i in xrange(1, limit+1):
+	if number_list[i-1]:
+		primes.add(i)
+
+
+def truncatable(n):
+	# right truncatable
+	tmp = n/10
+	while tmp > 0:
+		if not tmp in primes:
+			return False
+		tmp = tmp / 10
+
+	# left truncatable
+	tmp = n
+	modulo = 10**14
+	while tmp > 0:
+		if not tmp in primes:
+			return False
+		modulo = modulo / 10
+		tmp = tmp % modulo
+
+	return True
+
+
+result = []
+
+for p in primes:
+	if truncatable(p) and p not in (2, 3, 5, 7):
+		result += [p]
+
+print sum(result)
+