小O的质数 （Java代码）

解题思路:
    

    1. 设一个数为n,若n为非素数，则n存在因子在( 2...sqrt(n) ) (常规解法，速度较快)，但循环时依然从2到sqrt(n), 当n较大时，内循环的次数较多。实际上，在2...sqrt(n)的循环过程中，只有当被除数为素数时才会被执行。故，先使用数组存储2...sqrt(n)之间的素数，记为a.

    2. 循环L到R的过程中，偶数必然为非素数，故只循环奇数，循环次数可减少一半。

    3. 循环L到R的奇数时，内循环只判断数组a内的数据是否能被指定的数整除。

综上所述：从内外循环减少复杂度，可达到题目时间要求。
    



注意事项:

    2<=L<=R<=1000000000,R-L<=1000000

    测试数据：999000000 1000000000

    本机测试时间在 1.5s内, 但是不能AC本题，不知道什么原因，有清楚的麻烦告知一声。

参考代码:

import java.util.Scanner;

public class C1790 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int L = sc.nextInt(), R = sc.nextInt();
			
			//long t1 = System.currentTimeMillis();
			
			int maxSqrt = (int)Math.sqrt(R);
			int len = 1;
			if(maxSqrt - 2 >= 0){
				len = maxSqrt - 2 + 1;
			}
			
			int[] a = new int[len];
			int k = 0;
			for(int n = 2; n <= maxSqrt; n++){
				boolean isSu = true;
				for(int i = 2; i*i <= n; i++){
					if(n % i == 0){
						isSu = false;
						break;
					}
				}
				if(isSu){
					a[k++] = n;
				}
			}
			
			int count = 0;
			if(L <= 2){
				count++;
				L = 3;
			}else if(L % 2 == 0){
				L += 1;
			}
			for(int n = L; n <= R; n+=2){
				boolean isSu = true;
				for(int i = 0; i < a.length && a[i] > 0 && n != a[i]; i++){
					if(n % a[i] == 0){
						isSu = false;
						break;
					}
				}
				if(isSu){
					count++;
				}
			}
			System.out.println(count);
			
			//long t2 = System.currentTimeMillis();
			//System.out.println(t2-t1);
		}
		sc.close();
	}
}