From 0d39c1f1cae8c5e4f5f6bbab23fff7d8e36b4e7e Mon Sep 17 00:00:00 2001 From: Reiner Herrmann Date: Mon, 21 Jun 2010 16:51:58 +0200 Subject: projecteuler solution 46 --- src/projecteuler/046.py | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) create mode 100644 src/projecteuler/046.py 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 + -- cgit v1.2.3