C語言判斷是否爲素數（質數）

三個程式，判斷一個數是否爲素數，運算量依次遞減。

1. 簡單粗暴

//函數->判斷素數
bool IsPrime(int num)
{
	for (int i = 2; i < num; i++) {
		if (num % i == 0) return 0;
	}
	return 1;
}

int main()
{
	int n = 1234567;
	
	if (IsPrime(n)) {
		printf("YES\n");
	} else {
		printf("NO\n");
	}
	
	return 0;
}

2. 方法1的改進：回圈到sqrt（n）
   方法一是通過暴力回圈，依次判斷，其實沒必要判斷到n，而是判斷到sqrt（n）即可。因爲如果一個數可以分解爲兩個數的乘積的情況下，則一定是一個數在sqrt（n）的左側，一個數在sqrt（n）的右側，或者兩數相等，均爲sqrt（n）。因此，判斷sqrt（n）左側的數即可，判斷其能否被n整除。
   程式碼如下：

//函數->判斷素數
bool IsPrime(int num)
{
	for (int i = 2; i <= sqrt(num); i++) {
		if (num % i == 0) return 0;
	}
	return 1;
}

int main()
{
	int n = 1234567;
	
	if (IsPrime(n)) {
		printf("YES\n");
	} else {
		printf("NO\n");
	}
	
	return 0;
}

3. 如果存在素數，則該素數一定在6或6的倍數兩側
   如果一個數爲素數，則該素數一定在6或6的倍數兩側。這是一個充分不必要條件，即在6或6的倍數的兩側的數未必就是素數。
   程式如下：

//函數->判斷素數
bool IsPrime(int num)
{
	if (num == 2 || num == 3)   //排除兩個小素數
		return 1;
	
	if (num % 6 != 1 || num % 6 != 5)  //不在6或6的倍數兩側的均不是素數；
		return 0;
	
	for(int i = 5; i <= sqrt(num); i+=6) {
		if (num % i == 0 || num % (i+2) == 0) {
			return 0;
		}
	}
	return 1;
}

int main()
{
	int n = 1234567;
	
	if (IsPrime(n)) {
		printf("YES\n");
	} else {
		printf("NO\n");
	}
	
	return 0;
}