文章目錄

原题链接http://projecteuler.net/problem=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 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%?

螺旋素数
从1开始以如下方式逆时针螺旋,可以得到一个大小为7的螺旋方块

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

有趣的是奇数的平方都在对角线的右下角,更有趣的是,13个位于对角线的数中,有8个是素数;比率是8/13 约等于 62%。

如果像上面的螺旋那样再加一层螺旋,将得到一个大小为9的螺旋方块。如果这个步骤一直持续下去,当螺旋方块的大小为多少时,对角线上的素数比率会小于10%?

解答:
表示对角线上的数与第28题相同,最难的部分是判定一个数是否是素数,用动态生成素数表的方法不行,太大了。最后找到了米勒-拉宾素数测试法,很快。等以后有空时专门写一篇关于素数判定方法。

文章目錄