Project Euler 58

发表于 更新于 分类于 阅读次数： 本文字数： 761 阅读时长 ≈ 1 分钟

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 \(\dfrac{8}{13} \approx 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\%\)?

解决方案

这个矩阵的四个角的元素的通项公式分别是：\(4n^2-10n+7,4(n-1)^2+1,4n^2-6n+3,(2n-1)^2\)，其中\(n\ge 1\)，用的是第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)