AcWing 726. 质数-语法题-C++-详细

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 726. 质数-语法题-C++-详细原题链接中等

作者：

码 , 2021-07-15 17:50:58 , 所有人可见 , 阅读 7128

28

34

错误解法:

一般可能会这么写

这里的时间复杂度:O($XN$),计算量大概为:$10^9$,大概率会$\color{red}{TLE}$,应考虑对质数判定算法进行优化

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int j=1;j<=n;j++){
        int x;
        bool is_prime=true;
        cin>>x;
        if(x==1) cout<<x<<" is not prime"<<endl;
        else{
            int i;
            for(i=2;i<x;i++)
            {
                if(x%i==0) 
                {
                    is_prime=false;
                    break;
                }
                else is_prime=true;
            }
            if(is_prime) cout<<x<<" is prime"<<endl;
            else cout<<x<<" is not prime"<<endl;
        }
    }
    return 0;
}

正确解法:试除法判定一个数x是否为质数

时间复杂度:O($\sqrt{X}N$)
计算量大约为:$10^{5.5}$,可以$\color{red}{AC}$

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while (n -- ){
        int x;
        bool is_prime=true;
        cin>>x;
        if(x==1) cout<<x<<" is not prime"<<endl;
        else{
            int i;
            for(i=2;i<=x/i;i++)
            {
                if(x%i==0) 
                {
                    is_prime=false;
                    break;
                }
                else is_prime=true;
            }
            if(is_prime) cout<<x<<" is prime"<<endl;
            else cout<<x<<" is not prime"<<endl;
        }
    }
    return 0;
}

28 评论

litershry 2022-12-18 22:05

最后的100个 99999991真的恶心人啊

愿生无悔 2023-01-17 16:24

确实太恶心了

不也挺好的吗 2023-10-12 16:37

直接把第一个里面for(i=2;i<x;i++)的x换成i<x开方取整+1也行

不也挺好的吗 2023-10-12 16:38

或者写<=，不写+1

不也挺好的吗 2023-10-12 16:40

或者写i*i<=x也可以

仝 10个月前回复了不也挺好的吗的评论

大佬i*i<=x这个是什么意思啊，萌新看不懂😣

不也挺好的吗 9个月前回复了仝的评论

第二个写法里面的i<=x/i，把i挪到等式左边不就变成i×i<=x了。假设x不是质数，则有x=i×j，（假设i<=j，且i≠1），当i<j时i×i＜x。在检查所有可能的因子时，随着i增大，j会减小，i取最大值（假设能取到）时i=j，此时i×i=x。

仝 9个月前回复了不也挺好的吗的评论

谢谢大佬理解了🙏🌷

yao0224 2023-11-14 20:19

最后的100个 99999991真的恶心人啊

一条质疑水的鱼 2022-02-28 09:44

你好，想问一下为什么是i<=x/i呢

r.c.l 2022-03-02 22:53

因为只需要取最小的被除数就可以，只要知道一个约数i，x / i就是另一个约数

就像是2是被除数， 12 / 2 = 6， i就可以等于2

一条质疑水的鱼 2022-03-03 08:24 回复了 r.c.l 的评论

！！！好的！感谢

zxc23698 1个月前

#include[HTML_REMOVED]
using namespace std;
int main()
{
int n,x;
cin>>n;

while(cin>>x)
{
    bool is_prime = true;
    if(x==1)  cout<<x<<" is prime"<<endl;
else{
for(int i=2;i<x/i;i++)
{
    if(x%i==0)

      {   is_prime = false;
        break;}
    else is_prime =true;
}   
if(is_prime)
cout<<x<<" is prime"<<endl;
else
cout<<x<<" is not prime"<<endl;
}

system(“pause”):
return 0;

有没有大佬帮忙看下哪出了问题输入361运行不对

LeeHongdaat 9个月前

大佬！！！！！

897307710@qq.com 10个月前

#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
void judge(int x)
{
for(int i=2;i<=sqrt(x);i++)
{
if(x%i==0)
{
printf(“%d is not prime\n”,x);
return;
}
}
printf(“%d is prime\n”,x);
return;
}
int main()
{
int n;
cin>>n;
for(int i=0;i[HTML_REMOVED]>x;
judge(x);
}
return 0;
}

wos 11个月前

x本来就并不会是1为什么还判断一下

LiuHH 10个月前

x可以是1，只不过是不会执行后面的for循环，然后直接判断，最后得出的结果就是1是质数，只是这个题目中并没有1这个例子

欲共海棠俱醉 2023-12-05 21:44

#include[HTML_REMOVED]
using namespace std;
int main(){
int n;
cin>>n;
int x;
while(n–){
cin>>x;
int s=0;
if(x==1)cout<<x<<” is not prime”<<endl;
else{
for(int i=2;i<=sqrt(x);i++){
if(x%i==0)s=s+1;
}
if(s!=0)cout<<x<<” is not prime”<<endl;
else cout<<x<<” is prime”<<endl;
}
}
return 0;
}

未定 2023-11-14 09:58

但是我感觉上下两个实现功能的方法没有什么不同啊，差距竟会如此巨大

红色岛屿 2022-12-17 22:47

请问为什么加这句呢？else is_prime=true;

Pobz 2022-12-29 15:46

感觉加不加都可以，

seas 2022-11-05 15:23

#include [HTML_REMOVED]
using namespace std;

int main(){
int n;
cin>>n;
while(n–){

    int x;
    cin>>x;
    bool prime=true;
    for(int i=2;i*i<=x;i++){

        if(x%i==0){
            prime=false;
            break;
        }
    if(prime){cout<<x<<" is prime"<<endl;}
    else{cout<<x<<" is not prime"<<endl;}
    }
}
return 0;

}