PAT-B 1007. 素数对猜想 (20)

传送门

https://www.patest.cn/contests/pat-b-practise/1007

题目

让我们定义 dn为:dn = pn + 1- pn,其中 pi是第i个素数。显然有 d1=1 且对于n>1有 dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N (< 105),请计算不超过N的满足猜想的素数对的个数。
输入格式:每个测试输入包含1个测试用例,给出正整数N。
输出格式:每个测试用例的输出占一行,不超过N的满足猜想的素数对的个数。
输入样例:
20
输出样例:
4

分析

C++和Java实现方法都是:
运用筛选法求素数,也就是建立一个素数表,简单来说就是从2开始将2的倍数(不超过N)的下标对应的数组置为false,然后从3开始计算,直到超过N为止,然后遍历数组,根据true or false,判断素数的个数,最后输出即可。
这里我用的只是最低级的筛法,如果你想学习更高级的筛法建议搜索下相关资料。

源代码

//C/C++实现
#include <stdio.h>
#include <iostream>

using namespace std;

bool array[100000];

int main(){
    int n;
    scanf("%d", &n);
    for(int i=2;i<n/2+1;i++){
        for(int j=2;j*i<=n;j++){
            array[i*j] = true;
        }
    }
    int count = 0, tmp = 2;
    for(int k=2;k<=n;k++){
        if(array[k] == false){
            if(k - tmp == 2){
                count ++;
                tmp = k;
            }
            else{
                tmp = k;
            }
        }
    }
    printf("%d\n", count);
    return 0;
}

//Java实现
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String s = bufferedReader.readLine();
        int n = 0;
        try{
            n = Integer.valueOf(s);
        }catch(Exception e){
            System.exit(0);
        }
        if(n < 1 || n > 99999){
            System.exit(0);
        }
        int[] prime = new int[n+1];
        boolean[] isNotPrime = new boolean[n+1];
        for(int i=2;i<=n/2;i++){
            if(!isNotPrime[i]){
                for(int j=i*2;j<=n;j+=i){
                    isNotPrime[j] = true;
                }
            }
        }
        int size = 0;
        for(int k=2;k<=n;k++){
            if(!isNotPrime[k]){
                prime[size ++] = k;
            }
        }
        int count = 0;
        for(int i=0;i<prime.length-1;i++){
            if(prime[i+1]-prime[i] == 2){
                    count ++;
            }
        }
        System.out.println(count);
    }
}

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器