import random
from datetime import datetime
def is_prime3(q,k=50):
q = abs(q)
if q == 2: return True
if q < 2 or q&1 == 0: return False
d = (q-1)>>1
while d&1 == 0:
d >>= 1
for i in xrange(k):
a = random.randint(1,q-1)
t = d
y = pow(a,t,q)
while t != q-1 and y != 1 and y != q-1:
y = pow(y,2,q)
t <<= 1
if y != q-1 and t&1 == 0:
return False
return True
def Euler27():
max = 0
max_number = 0
a = [i for i in xrange(-1000, 1000) if (i % 2 ) == 1]
b = [i for i in xrange(1000) if is_prime3(i) == True]
for i in a:
for j in b:
if (i > -j) & (i < j):
n = 0
while (is_prime3(n*n + i * n + j) == True):
n+=1
if (n > max):
max = n
max_number = i * j
return max_number
def main():
start = datetime.now()
answer = Euler27()
end = datetime.now()
print end - start, answer
if __name__ == "__main__":
main()
