PAT-basic-1007 素数对猜想 java

一、题目

让我们定义d_n为：d_n =p_(n+1) − p~n，其中 p_i 是第 i 个素数。显然有 d₁=1，且对于n>1有d_n是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<10⁵)，请计算不超过N的满足猜想的素数对的个数。

输入格式:
输入在一行给出正整数N。

输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。

输入样例：
20
输出样例：
4

二、解析

用两个变量来表示迭代过程中遇到的相邻的素数。

三、代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int count = 0;
        int n = input.nextInt();
        int p1 = -1;
        int p2 = -1;
        for(int i=1; i<=n; i++){
            if (isPrime(i)) {
                p2 = p1;
                p1 = i;
                if(p1 - p2 == 2) count++;
            }
        }
        System.out.println(count);
    }
    public static boolean isPrime(int num){
        if(num == 1) return false;
        if(num == 2) return true;
        int limit = (int)Math.sqrt(num);
        for(int i=2; i<=limit; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}