博客

判断一个数字是否为素数有个基本条件

一个是不能和之前出现的所有数字下相除

另外一个简单条件就是不能和之前出现的素数相除，科学计算法已经证明：

素数不能被它的求根数之前的数相除

这样效率就大大提升了。

代码如下：

int IsPrime(int n) 
{ 
	int i; 
	if (n == 1 || n == 2 || n == 3 || n == 5) 
		return 1; 
	else if (n % 2) //排除了n是偶数的情况
	{ 
		for (i = 3; i <= n / 2 + 1; i += 2) //从3开始，总共判断n/2+1次
		{ 
			if (n % i == 0) return 0; 
		} 
		return 1; 
	} 
	else  
		return 0; 
	
}

这样就很容易判断了。