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]
去print
[Finished in 12.7s]
Prime list使用的场景也需要斟酌