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

Investigating a Prime Pattern 题号:146 难度: 50 中英对照

The smallest positive integer n for which the numbers n2+1, n2+3, n2+7, n2+9, n2+13, and n2+27 are consecutive primes is 10. The sum of all such integers n below one-million is 1242490.

What is the sum of all such integers n below 150 million?

Solution

如果$n=1\quad mod 2$,则$n^2+1=0\quad mod 2$,是合数。 所以$n=0\quad mod 2$。 如果$n=1\quad mod 5$,则$n^2+9=0\quad mod 5$,是合数。 如果$n=2\quad mod 5$,则$n^2+1=0\quad mod 5$,是合数。 如果$n=3\quad mod 5$,则$n^2+1=0\quad mod 5$,是合数。 如果$n=4\quad mod 5$,则$n^2+9=0\quad mod 5$,是合数。 所以$n=0\quad mod 5$。 则$n$是10的倍数。 暴力判断即可。

Code

public final class p146 {
    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 LIMIT = 150000000;
	private static long[] INCREMENTS = {1, 3, 7, 9, 13, 27};  // Must be in non-decreasing orde
	
	static public String run() {
		long sum = 0;
		for (int n = 0; n < LIMIT; n += 10) {
			if (hasConsecutivePrimes(n))
				sum += n;
		}
		return Long.toString(sum);
	}
	
	
	private static long maxNumber = (long)LIMIT * LIMIT + INCREMENTS[INCREMENTS.length - 1];
	private static int[] primes = listPrimes((int)(Math.sqrt(maxNumber)+1e-8));

    
	private static boolean hasConsecutivePrimes(int n) {
		// Generate the set of numbers to test for primality
		long n2 = (long)n * n;
		long[] temp = new long[INCREMENTS.length];
		for (int i = 0; i < INCREMENTS.length; i++)
			temp[i] = n2 + INCREMENTS[i];
		
		// Test that each number is prime.
		// Note: The nesting of the loops can be reversed, but this way is much faster.
		for (int p : primes) {
			for (long x : temp) {
				if (x != p && x % p == 0)
					return false;
			}
		}
		
		// Test that each number that is not an increment is composite.
		for (int i = 1; i < INCREMENTS[INCREMENTS.length - 1]; i++) {
			if (java.util.Arrays.binarySearch(INCREMENTS, i) < 0 && isPrime(n2 + i))
				return false;
		}
		return true;
	}
	
	
	private static boolean isPrime(long n) {
		int end = (int)(Math.sqrt(n)+1e-8);
		for (int p : primes) {
			if (p > end)
				break;
			if (n != p && n % p == 0)
				return false;
		}
		return true;
	}
	
	
	// Returns a Boolean array 'isPrime' where isPrime[i] indicates whether i is prime, for 0 <= i <= n.
		// For a large batch of queries, this is faster than calling isPrime() for each integer.
		// For example: listPrimality(100) = {false, false, true, true, false, true, false, true, false, false, ...} (array length 101).
		public static boolean[] listPrimality(int n) {
			if (n < 0)
				throw new IllegalArgumentException("Negative array size");
			boolean[] result = new boolean[n + 1];
			if (n >= 2)
				result[2] = true;
			for (int i = 3; i <= n; i += 2)
				result[i] = true;
			// Sieve of Eratosthenes
			for (int i = 3, end = (int)(Math.sqrt(n)+1e-8); i <= end; i += 2) {
				if (result[i]) {
					// Note: i * i does not overflow
					for (int j = i * i; j <= n; j += i << 1)
						result[j] = false;
				}
			}
			return result;
		}
		
		
		// Returns all the prime numbers less than or equal to n, in ascending order.
		// For example: listPrimes(97) = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 83, 89, 97}.
		public static int[] listPrimes(int n) {
			boolean[] isprime = listPrimality(n);
			int count = 0;
			for (boolean b : isprime) {
				if (b)
					count++;
			}
			
			int[] result = new int[count];
			for (int i = 0, j = 0; i < isprime.length; i++) {
				if (isprime[i]) {
					result[j] = i;
					j++;
				}
			}
			return result;
		}

}
676333270
95246ms