判断素数

看到一个利用数字6来判断一个自然数是否是素数。一个自然数可以写成fx=6*k+b(b=0,1,2,3,4,5)的形式。排除自然数为2或者3的特殊情况,我们可以看到b=0,2,3,4的时候都与6有公约数,所以这时候一定不是素数。也就是一个自然数除以6的余数是1或者是5的时候才有可能是素数。之所以说有可能是因为比较大的数字可能是多个的(6k+1)或(6k+5)的组合的乘积。比如25=5*5=(6*0+5)*(6*0+5),35=(6*0+5)*(6*1+1),只要在这个自然数除以6的余数为1或者5的情况下,排除掉其可能是2个或者多个较小的数(除以6的余数为1或者5的较小的数)的乘积。就可以确定这个数是否是素数了。

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 bool isprime(int num);
 5  
 6 int main()
 7 {
 8 for(int i=1;i<=100;i++)
 9 {
10     if(isprime(i)) cout<< i<<endl;
11 }
12 }
13 bool isprime(int num)
14 {
15     if(num<=1) return false; 
16     if(num==2 || num==3) return true;
17     if (num%6!=1&&num%6!=5) return false;
18     int tmp= sqrt(num);
19     for(int i=5;i<=tmp;i+=6)
20     {
21         if (num%i==0 || num%(i+2)==0) return false;
22     }
23     return true;
24 }