华师一附中OI组

标题: 试除法判断质数 [打印本页]

---

作者: admin    时间: 2019-1-7 09:19
标题: 试除法判断质数
判断质数一个很直观的方法就是看这个数字除了1和它本身之外还有没有其他的约数，那么我们可以拿2-sqrt(x)之间的数去除这个数，若有一个能被它整除，则说明不是质数，可以终止循环，否则继续判断到最后一个数字，若一个都没有找到，则说明x是质数。
这个程序段应该有两个出口，一个是找到了会提前结束，一个是到了sqrt(x)都没有找到，自动结束
代码段如下：

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int  x,i;
   
5. bool b;
   
6. int  main()
   
7. {
   
8.     cin>>x;
   
9.     i=2;
   
10.     b=1;
    
11.     while (i<=sqrt(x) && b)
    
12.         if (x%i==0) b=0;
    
13.         else i++;
    
14.     cout<<b;
    
15.     return 0;
    
16. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2