素数的快速判断方法

电玩女神 2022-01-28 10:41 301阅读 0赞

## 原理 ##

大于等于5的素数与6的倍数相邻

## 证明 ##

所有自然数可以用集合`A = { 6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5 }`表示，其中 `n >= 0`，显然，子集`B = {6n, 6n+2, 6n+3, 6n+4}`内的元素都不是素数，所以只有`6n+1`和`6n+5`可能是素数，素数一定可以用`6n+1`和`6n+5`其中的一个形式表示，即大于等于5的素数与6的倍数相邻 。

## 因子判断 ##

上面说到大于或等于5的素数一定可以用`6n+1`或者`6n+5`来表示，在判断一个数`num`是否是素数时，需要判断`num`是否有除1和自身之外的因子。这时只需要判断x是否是`num`的因子，其中`1 < x <= int(sqrt(num))`，而x的范围又可以用集合`{ 6i, 6i+1, 6i+2, 6i+3, 6i+4, 6i+5 }`表示。当`num`与6的倍数相邻时，`num`才可能是素数，因为`num`（奇数）和`{6i, 6i+2, 6i+3, 6i+4}`（偶数）互素，也就是`{6i, 6i+2, 6i+3, 6i+4}`不可能是`num`的因子，此时只需判断`x = 6i+1`和`x = 6i+5`是否是`num`的因子即可，如果都不是，则num是素数。

## C语言代码实现 ##

#include<stdio.h>
    #include<math.h>
    
    // 参数： num
    // 如果是素数，返回1，否则返回0
    
    int isprime(const int num) 
    { 
    	unsigned int i, half;
    	
    	if (num <= 1)
    		return 0;
    	if (num == 2 || num == 3)
    		return 1;
    	// 不和6的倍数相邻的数不是素数
    	else if (num % 6 != 1 && num % 6 != 5)
    		return 0;
    		
    	half = (unsigned int)sqrt(num);
    	for (i = 5; i <= half; i += 6)
    	{ 
    		if (num % i == 0 || num % (i + 2) == 0)
    			return 0;
    	}
    	return 1;
    }
    
    int main()
    { 
    	int num;
    	//printf("input num: ");
    	//scanf("%d", &num);
    	// 打印出1000以内的素数
    	for(num = 1; num < 1001; num++)
    	{ 
    		if(isprime(num))
    			printf("%d is prime.\n", num);
    		//else
    			//printf("%d is not prime.\n", num);
    	}
    	return 0;
    }