## 嵇爾的吐槽

#没事画轮子的嵇尔不定期的(W)碎(E)碎(B)念(B)和(L)吐(O)槽(G)

Problem 58 Spiral primes 2017-04-18 13:50:00

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

 37 36 35 34 33 32 31 38 17 16 15 14 13 30 39 18 5 4 3 12 29 40 19 6 1 2 11 28 41 20 7 8 9 10 27 42 21 22 23 24 25 26 43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

``````import math

def is_Prime(number):
if number < 2:
return False
for x in range(2, int(math.sqrt(number)) + 1):
if number % x == 0:
return False
return True

i = 0
pre = 0
count = 0

while True:
if i is 0:
count += 1
else:
size = i * 2 - 1
top_left = (i * 2)**2 + 1
top_right = top_left - 2 * i
bottom_left = top_left + 2 * i
#bottom_right = ((i * 2) + 1)**2
count += 4
if is_Prime(top_left):
pre += 1
if is_Prime(top_right):
pre += 1
if is_Prime(bottom_left):
pre += 1
print i * 2 + 1,
print pre, count,
rate = float(pre) / float(count)
print rate
if i > 0 and rate < 0.1:
break
i += 1
``````

[Finished in 16.5s]

[Finished in 12.7s]

Prime list使用的场景也需要斟酌