初識C語言==＞如何判斷一個數(shù)字是否為素數(shù)（質(zhì)數(shù)）？
2021-11-01 14:35:07

如何判斷素數(shù)

題目要求：輸出100-200的素數(shù)

首先我們要知道什么是素數(shù)（質(zhì)數(shù)），以防有人忘記（比如剛學(xué)開始學(xué)c的我就忘記了）

素數(shù)（質(zhì)數(shù)）只能被1和它自己整除

• 7只能被1和7整除，是素數(shù)
• 9能被3整除，不是素數(shù)

方法1—試除法

#include<stdio.h>

int main()
{
    int i=0;
    int count=0;
    for(i=100;i<=200;i++)
    {
        int j=0;
        for(j=2;j<i;j++)
        {
             if(i%j==0)//i可以整除j，i不是素數(shù)
             {
                 break;
             }
        }
        if(j==i)//i只能整除它自己，是素數(shù)
        {
            count++;
            printf("%d ",i);
        }
    }
    printf("
count=%d
",count);//計算100-200之間有幾個素數(shù)
    return 0;
}

這個代碼比較死，只是輸出了100到200之間的素數(shù)，完成了題目的要求

我們可以把它改造成輸入一個數(shù)字，判斷是否是素數(shù)的形式

---

代碼改造1-1

• 用戶輸入一個數(shù)字
• 代碼判斷是否為素數(shù)
• 是，輸出“是素數(shù)”以及用戶輸入的值
• 不是，輸出“不是素數(shù)”

#include<stdio.h>

int main()
{
    int i=0;
    int j=0;
    scanf("%d",&i);
    for(j=2;j<i;j++)
    {
    	if(i%j==0)
        {
            printf("不是素數(shù)
");
            break;
    	}
	}
    if(j==i)
    {
        printf("是素數(shù),i=%d
",i);
    }      
}

結(jié)果如下：

---

上面的這串代碼能很好地完成我們的需求，但它還有優(yōu)化的空間

方法2—開平方法

方法1中的for循環(huán)為j<i

如果數(shù)字很大的話，要循環(huán)非常多次才能出現(xiàn)j==i的情況

這就拖慢了我們程序運行的速度

這里我們引入一個概念

• 若i=a*b
• a和b中至少有一個數(shù)字 <= 開平方i

如16=2x8=4x4

其中2<4

這樣就能得到一個結(jié)論：

在根號i之前一定有一個數(shù)字n是非素數(shù)的除數(shù)

如果找不到這個數(shù)字n，說明該數(shù)字為質(zhì)數(shù)

---

利用開平方法，我們可以將需要查找的數(shù)字范圍縮小很多

以下是用該方法完成開頭題目要求的代碼示例

#include<stdio.h>

int main()
{
	int i=0;
	for(i=101;i<=200;i+=2)
	{
		int j=0;
		for(j=2;j<=sqrt(i);j++)
		{
			if(i%j==0)
			{
				break;
             }
		}
		if(j>sqrt(i))
		{
			printf("%d ",i);
		}
	}
	return 0;
}

將這個代碼改造成1-1那種形式也不難，自己試試吧！

---

感謝你看到最后

如果這篇博客對你有幫助，請點贊支持一下，萬分感謝！