Project Euler 58

Project Euler 58

题目

Spiral primes

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 81362%.

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%?

解决方案

这个矩阵的四个角的元素的通项公式分别是:4n210n+7,4(n1)2+1,4n26n+3,(2n1)2,其中 n1,用的是第 28 题的结论。

因此,这份代码将通过公式枚举出一个个质数,然后单独进行判断即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from tools import is_prime
from itertools import count

r = 0.1
c0 = 0
c1 = 1
for i in count(2, 1):
for x in [4 * i * i - 10 * i + 7, 4 * (i - 1) * (i - 1) + 1, 4 * i * i - 6 * i + 3, (2 * i - 1) ** 2]:
c1 += 1
if is_prime(x):
c0 += 1
if c0 / c1 < r:
ans = i * 2 - 1
break
print(ans)

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝