脚本宝典收集整理的这篇文章主要介绍了PAT乙级1007——素数对猜想，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目：

题目详情 - 1007 素数对猜想 (20 分) (pintia.cn)

 

分析：

这道题不难，但是还是耗费了我的一定时间（特别是最后调试的时候），我的思路有两种：

一、

把所有不大于N的素数都求出来，存储到一个数组里面（姑且称为a），递归这个数组，如果发现a[i]+2==a[i+1]，那么说明我们发现了一个素数对

二、

从2开始，求大于2小于N的各个奇数，如果某个数i是素数且i+2也是素数（i+2<=N），那么说明找到了一个素数对

实际操作，我先选择了思路二，代码如下，全部通过了：

#include <iostream>
#include <cmath>
int  IsPRime(int x)  //判断n是否为素数 
{
    if (x==2)
    {
        return 1;    //1和2是素数,return true
    } 
    else
    {
        int i;
        for (i=2;i<=sqrt(x);i++)
        {
            if (x%i==0)
            {
                return 0; //不是素数 
            }
        }
    }
    return 1;
}
int main()
{
    using namespace std;
    int n;
    cin>>n;        //读取数字n 
    int couple=0;  //素数对的个数
     
    for (int i=2;i<n;i++)
    {
        if (IsPrime(i))  //i是素数 
        {
            if (IsPrime(i+2)&&(i+2)<=n)  //i+2也是素数 
            {
                //cout<<i<<endl;
                couple++;
            }
        }
    }
    cout<<couple;
    return 0;
}

总结遇到的一些知识点：

1.0代表false 1代表true

@H_406_175@2.判断某个数是否是素数：1）从2开始再判断  2）用到sqrt函数，此函数在c语言里面在math.h中，在C++里面是cmath 3）注意循环退出条件

    判断素数这个函数太重要了！！！居然第一次写错了！！

    注意是 i<=sqrt(n)，不要忘了“=”（不然4就会判断错！！！）

反思反思：程序题写不快，有思路但是调试报错，唯一的解释就是：基础功不扎实！！！

下面是一个小优化：偶数不是素数，直接从3开始再算：

#include <iostream>
#include <cmath>
int  IsPrime(int x)  //判断n是否为素数 
{
    if (x==2)
    {
        return 1;    //1和2是素数,return true
    } 
    else
    {
        int i;
        for (i=2;i<=sqrt(x);i++)
        {
            if (x%i==0)
            {
                return 0; //不是素数 
            }
        }
    }
    return 1;
}
int main()
{
    using namespace std;
    int n;
    cin>>n;        //读取数字n 
    int couple=0;  //素数对的个数
     
    for (int i=3;i<n;i+=2)  //优化：2不是，偶数也不是 
    {
        if (IsPrime(i))  //i是素数 
        {
            if (IsPrime(i+2)&&(i+2)<=n)  //i+2也是素数 
            {
                //cout<<i<<endl;
                couple++;
            }
        }
    }
    cout<<couple;
    return 0;
}

题解二@H_126_353@

 

针对题解一中重复判断5是否为素数的问题，我们至少有两种方法解决：

 

@H_588_360@

建一个数组存储所有素数

用一个变量存储上一个素数且不断更新

 

网上搜到的题解有方法一，也有方法二，这里采用后者。

 

// PAT BasicLevel 1007
// https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int num);

int main()
{
    // 获取用户输入的数字
    int N=0;
    cin >> N;

    // 素数对的个数
    int count=0;

    // 上一个素数
    int lastPrime=2;    

    // 计算素数对个数
    for(int i=3;i<=N;i+=2){   // 偶数除了2一定不是素数
        // 找到新的素数
        if(isPrime(i)){
            
            // 判断是否为素数对
            if(i-lastPrime==2){ //两个素数之差为2
                count++;    // 计数
            }

            // 更新上一个素数
            lastPrime=i;
        }
    }

    // 输出结果
    cout << count;

    //System("pause");
    return 0;
}

// 判断是否为素数
bool isPrime(int num)
{
    // 1不是素数
    if(num<=1)
        return false;

    // 用这种方法找素数找的比较快，相当于i<sqrt(num)，但这样精度可能损失，导致错误
    for (int i = 2; i*i <= num; i++){
        if (num%i==0)
            return false;
    }

    return true;
    
}

来源：PAT乙级1007 - 臭咸鱼 - 博客园 (cnblogs.COM)

 

脚本宝典总结

以上是脚本宝典为你收集整理的PAT乙级1007——素数对猜想全部内容，希望文章能够帮你解决PAT乙级1007——素数对猜想所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。