判断质数

旧城等待， 2023-07-13 03:13 9阅读 0赞

## 判断质数 ##

> 方法一： 直接从2-（n-1）遍历一遍， 根据n%i判断，如果存在使得n%i == 0的则为false;否则为true,很简单，贴代码：

bool isPrime( int num )
    {
        
        for(int i= 2;i <= tmp-1; i++)
          if(num %i== 0)
             return false;
        return true;
    }

> 方法二：一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，所以并不需要遍历到n-1，遍历到sqrt(n)即可

bool isPrime( int num )
    {
        
         for(int i= 2;i <= sqrt(num); i++)
            if(num %i== 0)
              return 0 ;
         return 1 ;
    }

> 方法三：不记得从哪看到的了，是说： 关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；  
> 但在6的倍数相邻两侧并不是一定就是质数。  
> 此时判断质数可以6个为单元快进。  
> 即将方法（2）循环中i++步长加大为6，加快判断速度，原因是，假如要判定的数为n，则n必定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被6i，6i+2，6i+4整除，则n至少得是一个偶数，而偶数除了2都不是质数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，如果n能被6i+3整除，则n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。  
> 综上，循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为6，每次判断循环变量k和k+2的情况即可，理论上讲整体速度应该会是方法（2）的3倍。  
> 贴代码：

bool isPrime( int num )
    {
        
        //两个较小数另外处理
        if(num ==2|| num==3 )
            return true;
        //不在6的倍数两侧的一定不是质数
        if(num %6!= 1&&num %6!= 5)
            return false ;
        int tmp =sqrt( num);
        //在6的倍数两侧的也可能不是质数
        for(int i= 5; i <=tmp; i+=6 )
            if(num %i== 0||num %(i+ 2)==0 )
                return false ;
        //排除所有，剩余的是质数
        return true ;
    }