PAT乙级1007：素数对猜想

叁歲伎倆 2022-05-09 12:28 322阅读 0赞

题目：

70

解题思路：

把不超过N的素数全部保存在容器中，再验证相邻素数的差值是否为2.

题解：

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. int main()
  5. {
  6.     int n,cnt=0;
  7.     cin>>n;
  8.     vector<int> v;
  9.     for(int i=n;i>=1;i--)
  10.     {
  11.         int temp=1;
  12.         if(i%2==0&&i!=2)
  13.             temp=0;
  14.         else
  15.         {
  16.                 for(int j=2;j*j<=i;j++)//不需要验证到i
  17.             {
  18.                 if(i%j==0)
  19.                 {
  20.                     temp=0;
  21.                     break;
  22.                 }
  23.             }
  24.         }
  25.         if(temp)
  26.         {
  27.             v.push_back(i);
  28.         }
  29.     }
  30.     for(unsigned int i=0;i<v.size();i++)
  31.     {
  32.         if(v[i]-v[i+1]==2)
  33.             cnt++;
  34.     }
  35.     cout<<cnt<<endl;
  36. }

踩坑：

  • 在验证是否是素数的时候并不要验证到它本身i，只需要验证到sqrt(i)就行，这样能提高效率，避免超时。

发表评论

表情：
评论列表 （有 0 条评论，322人围观）

还没有评论，来说两句吧...

相关阅读

    相关 PAT B 1007 素数对猜想

    1007 素数对猜想 (20分) 让我们定义d​n​​为：d​n​​=p​n+1​​−p​n​​，其中p​i​​是第i个素数。显然有d​1​​=1，且对于n>1有d​n​

    灰太狼灰太狼/ 0 赞/ 83 阅读

    相关 PAT 1007 素数对猜想

    让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数

    小咪咪小咪咪/ 0 赞/ 237 阅读