高效判断素数算法(6倍原理)

末蓝、 2023-10-05 04:53 8阅读 0赞

# 原理： #

除了2和3外，其余素数都与6的倍数相邻，这些素数都满足6n±1，也就是说这些素数都分布在6的倍数的邻数上。总结为一句话：大于等于5的质数一定和6的倍数相邻。例如：5、7， 11、13、17等。但是与6的倍数相邻的不一定是素数，有可能是6倍邻数的倍数，例如25、35、49，这些数就分别是5，7的倍数。

**这是个trivial的素数分布特征，因模6的余数中只有1和5与6互素，故从5开始的素数必与6的倍数相邻。**

# 设计： #

算法设计的时候，除了2和3外需要判断一个数是否为素数。  
第一步：先判断是否为6倍邻数，如果是则执行第二步；  
第二步：判断这个数是否为6倍邻数的倍数，如若不是则这个数为素数

# 分析： #

### 1、大于等于5的素数必定为6倍邻数证明 ###

6倍以外的数分别有：6n+1，6n+2，6n+3，6n+4，6n+5  
其中6n+2，6n+3，6n+4三个数都可以分解：  
6n+2=2(3n+1)  
6n+3=3(2n+1)  
6n+4=2(3n+2)  
所以以上三个数必不可能是素数，剩下的只有6n+1，6n+5可能存在素数

### 2、6n+1和6n+5的素数判断 ###

**在判断6n+1和6n+5是否为素数过程中只需判断这个数是否为6倍邻数的倍数即可断定**

为何不需要判断这个数是否为6n+2，6n+3，6n+4的倍数  
首先，6n+2，6n+4为偶数，不可能是6n+1，6n+5这个两个奇数的因数，自然就不用判断  
然后，6n+3=3(2n+1)，所以6n+3必为3的倍数，3的倍数不分布在6n+1上，也不分布在6n+5上。  
因为

6 n + 1 3 = 2 n + 1 3 \\frac\{6n+1\}\{3\}=2n+\{ \{1\} \\over \{3\}\} 36n\+1=2n\+31  
 6 n + 5 3 = 2 n + 1 + 2 3 \\frac\{6n+5\}\{3\}=2n+1+\{ \{2\} \\over \{3\}\} 36n\+5=2n\+1\+32

当n为整数时，无论n取何值，上面这两个式子都不可能为整数。  
所以6n+1和6n+5，不可能为6n+3的倍数。  
故6n+1和6n+5，只可能为6m+1和6m+5的倍数。  
存在6倍邻数的两个因数是6倍邻数。

素数判断函数

bool isprime(int num) {
        
    	if (num == 2 || num == 3) {
        
    		return true;
    	}
    
    	//如果不与6的倍数相邻，肯定不是素数
    	if (num % 6 != 1 && num % 6 != 5) {
        
    		return false;
    	}
    
    	//对6倍邻数进行判断,是否为6倍邻数的倍数
    	for (int i = 5; i <= sqrt(num); i += 6) {
        
    		if (num % i == 0 || num % (i + 2) == 0) {
        
    			return false;
    		}
    	}
    	return true;
    }