projecteuler solution 46

1 files changed, 35 insertions, 0 deletions

diff --git a/src/projecteuler/046.py b/src/projecteuler/046.py
new file mode 100644
index 0000000..24a2983
--- /dev/null
+++ b/src/projecteuler/046.py
@@ -0,0 +1,35 @@
+
+from common import sieve
+
+squares = set([ x*x for x in xrange(1, 1000000) ])
+
+def check_number(number, prime):
+	square = (number - prime) >> 1
+	return square in squares
+
+prime_set = sieve(1000000).primes()
+primes = list(prime_set)
+primes.sort()
+
+number = 3
+
+while True:
+	number += 2
+
+	if number in prime_set:
+		continue
+
+	conjecture = False
+
+	for p in primes:
+		if p >= number:
+			break
+		if check_number(number, p):
+			conjecture = True
+			break
+
+	if not conjecture:
+		break
+
+print number
+