• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

PAT乙级1007——素数对猜想

开发技术 开发技术 5小时前 1次浏览

题目:

题目详情 – 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

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;
}

 

 

 

 

题解二

 

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

 

  1. 建一个数组存储所有素数
  2. 用一个变量存储上一个素数且不断更新

 

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

 

// 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——素数对猜想
喜欢 (0)