当前位置:首页 » Project Euler » 详细页

Spiral primes 题号:58 难度: 5 中英对照

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

Solution

观察示意图不难发现左上、左下、右上、右下对角线上数字的规律:假设边长为$~n~$,有 $$ 左上:n^2-2(n-1) $$ $$ 左下:n^2-1(n-1) $$ $$ 右上:n^2-3(n-1) $$ $$ 右下:n^2-0(n-1) $$ 即对角线上的数字为: $$ n^2-i(n-1),0 \leq i \leq 3 $$ 构造循环即可求解。

Code


import java.math.BigInteger;

public final class p058 {

    public static void main(String[] args) {
        long start = System.nanoTime();
        long result = run();
        long end = System.nanoTime();
        System.out.println(result);
        System.out.println((end - start) / 1000000 + "ms");
    }

    public static long run() {
        int numPrimes = 0;
        int n=3;
        while(true){
            for (int i = 0; i <= 3; i++) {
                if (isPrime(n * n - i * (n - 1))) {
                    numPrimes++;
                }
            }
            if (numPrimes * 10 < n * 2 - 1) {
                return n;
            }
            n+=2;
        }
    }

    public static boolean isPrime(int x) {
        if (x < 0) {
            throw new IllegalArgumentException("Negative number");
        }
        if (x == 0 || x == 1) {
            return false;
        } else if (x == 2) {
            return true;
        } else {
            if (x % 2 == 0) {
                return false;
            }
            int max = (int)Math.sqrt(x);
            for (int i = 3; i<= max; i += 2) {
                if (x % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }
}
26241
263ms