[已解决]这个素数判断看不懂，求解读

青出于蓝

#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
    int i=2,x;
    cin>>x; 
    for (;i*i<=x;i++)
        if(x%i==0)break; //实际上就是素数的判断
    cout<<x/i<<endl; //输出最大的因子，也就是最大的质数
    return 0; //程序君要休息了
} //END

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-1-13 22:37:07

青出于蓝 发表于 2023-1-13 22:34
感觉这个for循环不太常规啊
我写的：

由于题目中已经说了它是由两个质数相乘的来的，就不用去判断你得到的是不是质数了，因此，只需要先找到小的那个因数，再通过 原数/小因数 = 大因数即可

跳转到最佳答案楼层

tommyyu

这不是这一道题么https://www.luogu.com.cn/problem/P1075，不是素数判断吧

青出于蓝

tommyyu 发表于 2023-1-13 22:17
这不是这一道题么https://www.luogu.com.cn/problem/P1075，不是素数判断吧

感觉这个for循环不太常规啊
我写的：

#include<iostream>
#include<cmath>
using namespace std;
int zs(int n);
int main(){
    int p;
    cin>>p;
    for(int nn=p;nn>=sqrt(p);nn--){
        if((zs(nn)!=0)&&(p%nn==0)){
            cout<<zs(nn);
            return 0;
        }
    }
    
}
int zs(int n){
    if(!(n%2)){
        return 0;
    }
    for(int i=n-1;i>=sqrt(n);i-=2){
        if((n%i)==0){
            return 0;
        }
    }
    return n; 
}

我的效率很低的样子，但和上边的好像没什么大区别

ExiaGN001

这个代码的出处是否为：https://www.luogu.com.cn/problem/P1075

tommyyu

青出于蓝 发表于 2023-1-13 22:34
感觉这个for循环不太常规啊
我写的：

由于题目中已经说了它是由两个质数相乘的来的，就不用去判断你得到的是不是质数了，因此，只需要先找到小的那个因数，再通过 原数/小因数 = 大因数即可

青出于蓝

tommyyu 发表于 2023-1-13 22:37
由于题目中已经说了它是由两个质数相乘的来的，就不用去判断你得到的是不是质数了，因此，只需要先找到小 ...

感谢，一针见血，

niuniu97

cin>>x; -------------这里就是输入一个数x，我们要计算这个数是不是素数
    for (;i*i<=x;i++)  ---------------- 循环，i从2开始，到根号x结束。因为素数就是除了1和自身，都不能整除。算到根号x就够了
        if(x%i==0)break; -------------如果整除了，那就不是素数了，那就结束
    cout<<x/i<<endl;    -------循环结束都没break，说明就是素数，输出就好了。