转载

1007 素数对猜想 (20 分)java

让我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i个素数。显然有d​1​​=1,且对于n>1有d​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

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

输入格式:

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

输出格式:

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

输入样例:

20

输出样例:

4

code

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int N = (int) in.nval , k = 0 , count = 0;
        int[] arr = new int[N + 1];

        for(int i = 2 ; i <= N ; i++) {
            int j = 2;
            for( ; j <= Math.sqrt(i) ; j++) {
                if(i % j == 0)
                    break;
            }
            if(j > Math.sqrt(i))
            {
                arr[k++] = i;
            }
        }
        for(int i = 0 ; i < N ; i++) {
            if(arr[i + 1] - arr[i] == 2){
                count++;
            }
        }
        out.println(count);
        out.flush();
    }
}
原文  https://segmentfault.com/a/1190000017968373
正文到此结束
Loading...