C語言中如何判斷質(zhì)數(shù)

更新時間：2023年03月03日 09:53:44 作者：胖大斯

這篇文章主要介紹了C語言中的判斷質(zhì)數(shù)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

C語言判斷質(zhì)數(shù)

寫判斷質(zhì)數(shù)的程序時，需特別注意邊界條件：

1.開始邊界條件：2作為第一位質(zhì)數(shù)，不參與循環(huán)；

2.循環(huán)主體：divisor += divisor % 2 +1代表當(dāng)除數(shù)divisor是奇數(shù)時+2，是偶數(shù)時+1；

3.結(jié)束邊界條件：當(dāng)divisor趨近n時，即divisor=n-1或divisor=n-2，仍然沒有數(shù)能被n整除，那么可以判斷n為質(zhì)數(shù)

#include <stdio.h>
int main() {
    int divisor;
    int n;
    scanf("%d",&n); // 輸入要判斷的數(shù)
    if (n == 2) {
        printf("YES"); 
    } else {
        for (divisor = 2; divisor < n; divisor += (divisor % 2 + 1) ) {
            if (n % divisor == 0) {
                printf("NO"); // 當(dāng)出現(xiàn)能被1或自身之外整除時
                break;
            } else if (divisor == n - 1 || divisor == n-2) {
                printf("YES"); // 循環(huán)到 n-1 或 n-2 時，仍然沒有被其他數(shù)整除
            }
        }
    }
    return 0;
}

C語言判斷素數(shù)的函數(shù)

下列程序?qū)懥艘粋€判別素數(shù)的函數(shù)，在主函數(shù)輸入一個整數(shù)，輸出是否為素數(shù)的信息。

#include <stdio.h>?
int main()
? ?{
? ? ? int prime(int);
? ? ? int n;
? ? ? printf("請輸入一個整數(shù)：");
? ? ? scanf("%d",&n);?? ?
? ? ?if______________________ ? ? ? ? ? ? ? ??
?? ? ? ? printf("%d 是素數(shù)。\n",n);
? ? ?else
?? ? ? ? printf("%d 不是素數(shù)。\n",n);
? ? ?return 0;
? ?}
? int prime(int n)
? {
? ? ?int flag=1,i;
? ? ?for(i=2;i<n/2&&flag==1;i++)
? ? ?if ______________________ ? ? ? ? ? ? ? ? ??
? ? ?flag=0;
? ? ?________________________;
? ? }

經(jīng)分析，以上代碼使用flag的值來判斷輸入的n是否為素數(shù)，flag=1，n為素數(shù)；flag=0,n不是素數(shù)。完善if條件語句，第一個if, 主函數(shù)中的if調(diào)用函數(shù)，需要填入一個參數(shù)，即prime(n); 第二個if,是判斷什么情況下flag=0，即輸入的整數(shù)不為素數(shù)，即(n/i==0),余數(shù)為0，可以整除；最后返回flag的值，return flag。

但是經(jīng)過運(yùn)行可以知道，n=4的時候，程序判斷4是素數(shù)，明顯是錯誤的，n取0和1的時候同理，程序存在漏洞。

分析得知，在定義函數(shù)的過程中，for循環(huán)條件語句，i<=n/2&&flag==1才能正確運(yùn)行，同時添加if語句對0和1判斷。（前提輸入的n>=0，如果為負(fù)整數(shù)，另加判斷條件，略）

正確代碼如下

#include <stdio.h> 
int main()
   {
    int prime(int);//函數(shù)聲明
    int n;
    printf("請輸入一個整數(shù)：\n");
    scanf("%d",&n);	
    if(prime(n))
	{    
        printf("%d 是素數(shù)。\n",n);
    }else
    {
        printf("%d 不是素數(shù)。\n",n);
    }
    return 0;
   }
int prime(int n)  //函數(shù)定義
{
    int flag = 1,i;
    if (n <= 1)  //判斷0和1，需要先排除
       flag = 0; //返回0值
    for(i=2;i <= n/2 && flag == 1;i++) //n無法整除比n/2大的數(shù),flag=1為真，即為素數(shù)，繼續(xù)執(zhí)行
        if (n%i == 0)                 //如果取余為0，則其可以整除，不是素數(shù)。
        flag=0;                     //標(biāo)記flag=0,非素數(shù)。
    return flag;
}