问题标题: 酷町堂:1264

0
0
已解决
汪恺恒
汪恺恒
中级启示者
中级启示者

题目描述 Description

两个相差为2的素数称为素数对,如3和5,5和7等,输入一个数N,找出所有两个数均不大于N的素数对。

输入描述 Input Description

输入一个正整数N,1=<N<=10000

输出描述 Output Description

输出所有小于等于N的素数对。每对素数对输出一行, 中间用一个空格隔开。若没有找到任何素数对,则输出“Error”。

90分!

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
bool flag=0;
bool ss(int k){
    if(k==1){
        return false;
    }
    for(int i=2;i<=sqrt(k);i++){
        if(k%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        if(ss(i)&&ss(i+2)){
            cout<<i<<" "<<i+2<<endl;
            flag=1;
        }
    }
    if(cnt==0){
        cout<<"Error";
    }
    return 0;
}

 


0
已采纳
周琪岳
周琪岳
资深光能
资深光能

i+2会大于n,这就是错误原因

应改成这样for(int i=1;i<=n-2;i++)

不过这样时间复杂度为O(n^2),可以用埃氏筛法优化,详细的我到学校再叫你

周琪岳在2020-11-30 17:23:09追加了内容

cnt得改成f2

0
崔竣恺
崔竣恺
中级守护
中级守护
首先,cnt要改成你的标志位f2

然后,如果i+2大于n了呢?判断条件要加上一个i+2<=n

即可AC

这是你的main函数内部的代码修改后:

main(){

cin>>n;

for(int i=1;i<=n;i++){

if(ss(i)&&ss(i+2)&&i+2<=n){

cout<<i<<" "<<i+2<<endl;

flag=1;

}

}

if(f2==0){

cout<<"Error";

}

return 0;

}

0
李显晨
李显晨
中级启示者
中级启示者

你的问题:

1、22行的if里的条件要改成这样:

if(ss(i)&&ss(i+2)&&i+2<=n)

2、27行的cnt是从哪来的???应该是:

if(!flag)

 

0
我要回答