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

Prime square remainders 题号:123 难度: 30 中英对照

Let pn be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder when (pn−1)n + (pn+1)n is divided by pn2.

For example, when n = 3, p3 = 5, and 43 + 63 = 280 ≡ 5 mod 25.

The least value of n for which the remainder first exceeds 109 is 7037.

Find the least value of n for which the remainder first exceeds 1010.

Solution

此题求解需要用到第120题的结论,我们知道: - 当n是偶数时, $$ (a-1)^n +(a+1)^n mod \ a^2 =2 $$ - 当n是奇数时, $$ (a-1)^n +(a+1)^n mod \ a^2 =2 \cdot a \cdot n $$ $\because$ 2 很小,计算时直接跳过$n$取偶数的情况,先利用前面用到很多次的**PrimeSeive方法**求出 一定范围内的质数数组,然后遍历,该数组,找到第一个满足阈值$T=10^{10}$的质数,利用 $$ 2 \cdot a \cdot n \geq T $$ 其中 $n$是primes数组下标,$a$是对应下标的数组元素。

Code

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


    private static final int PRIME_LIMIT = 1000000;
    private static final long THRESHOLD = 10000000000L;

    public static  String run() {
        int[] primes = getPrimes(PRIME_LIMIT);
        for (int n = 5; n <= primes.length; n += 2) {
			/*
			 * Using the result from Project Euler #120, we know that
			 * (a-1)^n + (a+1)^n mod a^2 = if n is even then 2 else 2an.
			 * Since 2 is tiny, we can skip the n is even case.
			 * a is the n'th (1-based) prime number, so a > n. In fact for n >= 5,
			 * we have a > 2n, so we can take 2an directly without moduloing it by a^2.
			 */
            long rem = (long)n * primes[n - 1] * 2;
            if (rem > THRESHOLD)
                return Integer.toString(n);
        }
        throw new AssertionError("Not found");
    }


    private static int[] getPrimes(int N) {
        boolean[] isPrime = new boolean[N + 1];
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }
        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i; i * j <= N; j++) {
                    isPrime[i * j] = false;
                }
            }
        }
        int primeCount = 0;
        for (int i = 2; i <= N; i++) {
            if (isPrime[i])
                primeCount++;
        }
        int[] primes = new int[primeCount];
        int k = 0;
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) {
                primes[k] = i;
                k++;
            }

        }
        return primes;
    }

}
21035
14ms