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 Euler58():
Prime_total = 8.
count = 6.
Num = 49.
Total = 13.
while (Prime_total / Total) >= 0.1:
count += 2.
for i in xrange(4):
Num = count + Num
Total += 1.
if is_prime3(int(Num)) == True:
Prime_total += 1.
return int(count + 1)
def main():
start = datetime.now()
answer = Euler58()
end = datetime.now()
print end - start, answer
if __name__ == "__main__":
main()
