C語言求給定範圍內的所有素數代碼及解析

問題描述

求給定範圍start〜end之間的所有素數。

問題分析

判定一個整數m是否為素數的關鍵就是要判定整數m能否被除1和它自身以外的任何其他整數所整除，若都不能整除，則m即為素數。

本題求的是給定範圍start〜end之間的所有素數，考慮到程序的通用性，需要從鍵盤上輸入start和end值，例如輸入start=1，end=1000，則所編寫的程序應能夠列印出1〜1000之間的所有素數。

算法設計

由問題分析可知，該問題考慮用雙層循環結構實現。

外層循環對start〜end之間的每個數進行迭代，逐一檢查其是否為素數。外層循環的循環變量用變量m表示，m即代表當前需要進行判斷的整數，顯然其取值範圍為start≤m≤end。

內層循環稍顯複雜，完成的功能是判斷當前的m是否為素數。設內循環變量為m，程序設計時i從2開始，直到為止。用i依次去除需要判定的整數m，如果m能夠被中的任何一個整數所整除，則表示i必然小於或等於，則可以確定當前的整數m不是素數，因此，應提前結束該次循環。如果n不能被中的任何一個整數所整除，則在完成最後一次循環後，i還需要加1，即，之後才終止循環。此時，可以確定當前的整數m為素數。

可以使用標誌位flag來監控內外循環執行的情況。在定義變量時將flag初值設為1，在內層循環中判斷時，如果m能夠被中的任何一個整數所整除，則在內循環中將flag設置為0。如果m不能被中的任何一個整數所整除，則在內循環中不會修改flag標誌的值，退出內循環後它的值仍為1。此時在外循環中對flag的值進行判斷，如果flag=0，則顯然當前的m不是素數，如果flag=1，則當前的m是素數，應該將其列印出來。

還需要注意的是，在外循環中，每次要進行下一次迭代之前，要先將flag標誌再次置為1。

程序流程圖：

下面是完整的代碼：

#include<stdio.h>
#include<math.h>
int main()
{
    int start, end, i, k, m, flag=1, h=0;
    do
    {
        printf("輸入 起始數字 和 結束數字:");
        scanf("%d%d", &start, &end);
    }while(!(start>0 && start<end));
    printf(".... (%d-%d)素數列表....\n", start, end);
    for(m=start; m<=end; m++)
    {
        k=sqrt(m);
        for(i=2; i<=k; i++)
            if(m%i==0)
            {
                flag=0;
                break;
            }
        if(flag)
        {
            printf("%-4d",m);
            h++;
            if(h%10==0)
                printf("\n");
        }
        flag=1;
    }
    printf("\n共有%d個素數\n", h);
    return 0;
}

運行結果：

輸入 起始數字 和 結束數字:1 200
.... (1-200)素數列表....
1  2  3  5  7  11  13  17  19  23 
29  31  37  41  43  47  53  59  61  67 
71  73  79  83  89  97  101 103 107 109
113 127 131 137 139 149 151 157 163 167
173 179 181 191 193 197 199
共有47個素數

Linux公社的RSS地址：https://www.linuxidc.com/rssFeed.aspx

本文永久更新連結地址：https://www.linuxidc.com/Linux/2018-11/155472.htm