PAT (Basic Level) Practice 1007 素数对猜测

manbetx手机网页版私练习

1007. 素数对猜想 (20)

为咱定义 dn 为:dn = pn+1 – pn,其中 pi 是第i只素数。显然起 d1=1
且对n>1发
dn 是偶数。“素数对怀疑”认为“存在无穷多对附近且不同吧2的素数”。

即为得任意正整数N (< 105),请计算不越N的满足猜想的素数对的个数。

输入格式:每个测试输入包含1单测试用例,给闹刚刚整数N。

出口格式:每个测试用例的输出占一行,不跳N的满足猜想的素数对的个数。

输入样例:

20

出口样例:

4

manbetx手机网页版 1manbetx手机网页版 2

 1 #include<iostream>
 2 #include<math.h>
 3 #include<vector>
 4 using namespace std;
 5 int main(){
 6      int N,n;
 7      cin>>N;
 8      vector<int> vi;
 9      for(int j=3;j<=N;j++){
10          int flag=1; n=sqrt(j);
11          for(int i=2;i<=n;i++){
12           if(flag==0) break;
13           if(j%i==0) flag=0;
14          }
15         if(flag==1) vi.push_back(j);
16      }
17      int cnt=0;
18      for(auto b=vi.begin()+1;b<vi.end();b++)
19      if(*b-*(b-1)==2) cnt++;
20      cout<<cnt;
21      return 0;
22 } 

View Code

 


 

给我们定义d​n​​为:d​n​​=p​n+1​​−p​n​​,其中p​i​​是第i独素数。显然起d​1​​=1,且对n>1出d​n​​是偶数。“素数对怀疑”认为“存在无穷多对附近且不同啊2的素数”。

现为得任意正整数N(<),请计算不超N的满足猜想的素数对的个数。


 

输入格式:

输入在一行于闹刚刚整数N

出口格式:

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


输入样例:

20

输出样例:

4

#include<stdio.h>
#include<math.h>

int isPrime(int x)
{
  if(x==1 || x==0)
    return 0;
  if(x==2)
    return 1;
  int tmp=(int)sqrt((double)x);
  for(int i=2;i<=tmp;i++)
  {
    if(x%i==0)
      return 0;
  }
  return 1;
}

int main(){
  int n;
  int count=0;
  scanf("%d",&n);
  for(int i=2;i<=n-2;i++)
  {
    if(isPrime(i)==1 && isPrime(i+2)==1)
      count++;

  }
  printf("%d\n",count);
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图