一、题目
二、算法
1、建立一个判断是否是素数的缓存表，只存储sqrt(最大偶数)/2个数，因为sqrt(最大偶数)中有一半都是偶数。
import java.util.Scanner; public class Test { private static final int[] PRIMES_CACHE = new int[(int)Math.sqrt(10000000)/2]; private static int count = 0; public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); if (n == 0) { return; } int[] evens = new int[n]; for (int i = 0; i < n; i++) { evens[i] = in.nextInt(); } long start = System.currentTimeMillis(); int maxEven = evens[n - 1]; check(maxEven); int[] counts = new int[n - 1]; for (int i = 0; i < n - 1; i++) { int pre = evens[i]; int next = evens[i + 1]; int c = 0; for (int j = pre + 1; j < next; j += 2) { if (isPrime(j)) { c++; } } counts[i] = c; } long sum = 0; for (int d = 0; d < counts.length; d++) { for (int i = 0; i < counts.length; i++) { int k = i + d; if (k < counts.length) { for (int l = i; l <= k; l++) { sum += counts[l]; } } } } long flow = System.currentTimeMillis() - start; System.out.println(sum); System.out.println(flow/1000.0); } } public static boolean isPrime(int x) { if (x == 2) { return true; } int sqrt = (int) Math.sqrt(x); for (int i = 0; i < count && PRIMES_CACHE[i] <= sqrt; i++) { if (x % PRIMES_CACHE[i] == 0) { return false; } } return true; } public static void check(int maxInput) { int maxSqrt = (int) Math.sqrt(maxInput); if (count != 0 && maxSqrt <= PRIMES_CACHE[count - 1]) { return; } int next; if (count == 0) { next = 3; } else if (maxSqrt > PRIMES_CACHE[count - 1]) { next = PRIMES_CACHE[count - 1] + 2; } else { return; } for (int i = next;i<=maxSqrt; i += 2) { if (isPrime(i)) { PRIMES_CACHE[count++] = i; } } } } 2、筛选素数法 package com.test; import java.util.BitSet; import java.util.Scanner; public class Main5 { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); int[] evens = new int[n]; for (int i = 0; i < n; i++) { evens[i] = in.nextInt(); } long start = System.currentTimeMillis(); int maxEven = evens[n - 1]; BitSet bitSet = new BitSet(maxEven); bitSet.set(2); for(int i=3;i<maxEven;i+=2){ bitSet.set(i); } for(int i=3;i*i<maxEven;i+=2){ if(bitSet.get(i)){ for(int j=i*i;j<maxEven;j=j+i+i){ bitSet.clear(j); } } } int[] counts = new int[n-1]; for (int i = 0; i < n - 1; i++) { int l = evens[i]; int r = evens[i + 1]; int c =0; for(int j=l+1;j<r;j++){ if(bitSet.get(j)){ c++; } } counts[i] = c; } long sum = 0; for (int d = 0; d < counts.length; d++) { for (int i = 0; i < counts.length; i++) { int k = i + d; if (k < counts.length) { for (int l = i; l <= k; l++) { sum += counts[l]; } } } } System.out.println(sum); System.out.println((System.currentTimeMillis() - start)/1000.0); } } } 三、运行时间1、缓存筛选表方法
2、筛选法
