C語言|程式設計|判斷素數

#1 素數定義

素數又叫質數（prime number），定義為在大于1的自然數中，除1和它本身外不再有其他因數。

#2 程式設計實作（最普通）

判斷一個數a是否為素數，隻需用a對2到(a-1)範圍内的數求模。隻要有一個模為0，則a不是素數。

#include<stdio.h>

int main()
{
	int num = 0;
	int tmp = 2;
	int flag = 1; // 假設輸入的數是素數，後面再判斷
	printf("請輸入一個正整數(大于2)：");
	scanf("%d", &num);
	
	for (; tmp < num; tmp++) // 依次跟2~(num-1)取模
	{

		if (num % tmp == 0) //如果有num % tmp 等于0，說明有其他因數，是以這個數不是素數
		{
			flag = 0; //等于0，也就是不是素數
			break;
		}
	}
	if (flag == 1)
	{
		printf("%d是素數\n", num);
	}
	else
	{
		printf("%d不是素數\n", num);
	}

	return 0;
}
           

#3 優化

可以對上面的代碼進行優化，

①首先素數不可能是偶數，因為偶數有2這個因數

②如果一個數m 有因數，則至少有一個因數是小于或等于m的開平方

#include<stdio.h>

int main()
{
	int num = 0;
    int tmp = 2; 
	int flag = 1; // 假設輸入的數是素數，後面再判斷
	printf("請輸入一個正整數(大于2)：");
	scanf("%d", &num);
	
	for (; tmp <= sqrt(num); tmp++) // 依次跟2~(num-1)取模
	{
        if(num % 2 == 0) //判斷是否為偶數
        {
            flag = 0;
            break;
        }

		if (num % tmp == 0) //如果有num % tmp 等于0，說明有其他因數，是以這個數不是素數
		{
			flag = 0; //等于0，也就是不是素數
			break;
		}
	}
	if (flag == 1)
	{
		printf("%d是素數\n", num);
	}
	else
	{
		printf("%d不是素數\n", num);
	}

	return 0;
}
           

#4 再優化

#include <stdio.h>
#include <stdbool.h>

int main()
{
	int num = 0;
	int tmp = 2;
	bool isPrime = true; // 假設輸入的數是素數，後面再判斷

	printf("請輸入一個正整數(大于2)：");
	while ((scanf("%d", &num)) == 1)
	{
		for (tmp = 3, isPrime = true; tmp <= sqrt(num); tmp+2)
		{
			if (num % 2 == 0) //判斷是否為偶數
			{
				isPrime = false;
				break;
			}
			if (num % tmp == 0)
			{
				isPrime = false;
				break;
			}
		}
		if (isPrime)
		{
			printf("%d是素數\n", num);
		}
		else
		{
			printf("%d不是素數\n", num);
		}
	}
	return 0;
           

以上代碼可以實作多次輸入。