问题
如下所示,从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》的是一样的,只是旋转的方向不一样。所以那套计算对角线数字的公式是可以照搬的。
如果想用筛选法先求出范围内的素数,这可能需要一些运气才可以求到上界。
由于这个问题暴力解题就可以了,所以就不碰运气了,直接用试除法吧,这样不需要猜那个上界值。
答案
// answer: brute force
const start = Date.now()
function is_prime(n) {
if (n == 2 || n == 3 || n == 5 || n == 7)
return true
else if (n < 2)
return false
if ((n % 2) == 0)
return false
const end = Math.sqrt(n)
for (let i = 3; i <= end; i += 2)
if ((n % i) == 0)
return false
return true
}
let result = 0
for (let d = 3, prime_count = 0, diagonal_count = 1; true; d += 2) {
const gap = d - 1
for (let num = d*d - gap, i = 0; i < 3; ++i, num -= gap)
if (is_prime(num))
prime_count++
diagonal_count += 4
if (prime_count/diagonal_count < 0.1) {
result = d
break
}
}
alert(result + ', ' + (Date.now() - start) + 'ms')
打赏作者