1007. 素数对猜想

让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数

，请计算不超过N的满足猜想的素数对的个数。（简书markdown不支持）

输入格式：每个测试输入包含1个测试用例，给出正整数N。

输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例：

20

输出样例：

4

idea：

• 这题比较简单但是得考虑到查找素数的效率问题，双重for循环来筛选素数，再用前后两个素数想减是否等于2判断。
• 普通方法会造成运行超时，用二分查找也是，干脆用开平方根来查找。

代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner shuru=new Scanner(System.in);
        int number=shuru.nextInt();
        int result=0;
        int suone=0;
        int sutwo=0;
        for (int i = 2; i < number; i++) {
            boolean flag=true;
            for (int j = 2; j <=Math.sqrt(i); j++) {
                if(i%j==0){
                    flag=false;
                    break;
                }
            }
            if(flag){
                suone=i;
                if(i-sutwo==2){
                    result+=1;
                }else{
                    sutwo=suone;
                }
            }
        }
        System.out.println(result);
    }
}