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.

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);
}
}

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