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

青出于蓝

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int main()
   
5. {
   
6.     int i=2,x;
   
7.     cin>>x;
   
8.     for (;i*i<=x;i++)
   
9.         if(x%i==0)break; //实际上就是素数的判断
   
10.     cout<<x/i<<endl; //输出最大的因子，也就是最大的质数
    
11.     return 0; //程序君要休息了
    
12. } //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循环不太常规啊
我写的：

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int zs(int n);
   
5. int main(){
   
6.     int p;
   
7.     cin>>p;
   
8.     for(int nn=p;nn>=sqrt(p);nn--){
   
9.         if((zs(nn)!=0)&&(p%nn==0)){
   
10.             cout<<zs(nn);
    
11.             return 0;
    
12.         }
    
13.     }
    
14.    
    
15. }
    
16. int zs(int n){
    
17.     if(!(n%2)){
    
18.         return 0;
    
19.     }
    
20.     for(int i=n-1;i>=sqrt(n);i-=2){
    
21.         if((n%i)==0){
    
22.             return 0;
    
23.         }
    
24.     }
    
25.     return n;
    
26. }

复制代码

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

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，说明就是素数，输出就好了。