C 語言輸出100至200之間的質數（素數）

題目描述

執行 C 程式，輸出 100 至 200 之間的質數。

輸入描述

無

輸出描述

輸出 100 至 200 之間的質數，每行輸出一個質數，每個質數前面需要帶有序號。

輸出樣例

解題思路

在《一文解決如何使用 C 語言判斷質數（素數）》一文中，我詳細講解了質數以及如何使用 C 語言判斷質數，本篇文章將參照此文中判斷質數的函數，共介紹了兩種判斷方法，分別是暴力求解和巧用平方根，出於對程式執行效率的考慮，在這裡我以巧用平方根為例進行講解。

方案一

• 首先我們將巧用平方根判斷質數的函數複製到程式中。
• 然後利用 for 迴圈遍歷 100 至 200 之間的數，逐一判斷哪個是質數。
• 找出質數後，將儲存質數個數的變數自加 1，並將此變數和該質數輸出。

具體程式碼如下：

#include <stdio.h>
#include <math.h>   /* 包含 <math.h> */

/****************************************************************************
* 函數名：  Judge_PrimeNumber
* 功能描述：判斷一個數是否為質數
* 輸入引數：
*			_number：需要判斷的數
* 返回值：
*			1：是質數
*			0：不是質數
* 外部引數：無
* 注意事項：無
*
* 作者：	樑國慶
* 日期：	2021-12-11
* 修改記錄：
****************************************************************************/
int Judge_PrimeNumber(int _number)
{
    int i = 0;

    if (_number < 2)
    {
        return 0;   /* 需要判斷的數小於 2，則不是質數，返回 0 */
    }

    for (i = 2; i <= sqrt(_number); i++)    /* 遍歷從 2 到 √_number 區間中的所有數 */
    {
        if (_number % i == 0)
        {
            return 0;                       /* 若可以被整除，則不是質數，返回 0 */
        }
    }

    return 1;       /* 若執行完以上程式均未返回，則是指數，返回 1 */
}

int main()
{
    int i = 0, num = 0;

    for (i = 100; i <= 200; i++)        /* 遍歷 100 至 200 之間的數 */
    {
        if (Judge_PrimeNumber(i) == 1)  /* 呼叫判斷質數的函數，判斷輸入的整數 i */
        {
            num++;

            printf("%d.\t", num);       /* 輸出當前質數的個數 */
            printf("%d\n", i);          /* 輸出質數 */
        }
    }

    return 0;
}

方案二

本方案是對方案一的優化處理。

在 100 至 200 之間的所有偶數都不是質數，所以可以將其去除，直接對奇數進行判斷，對於方案一來說可以讓程式的執行時間減少一半，執行效率大幅度提高。

具體程式碼如下：

#include <stdio.h>
#include <math.h>   /* 包含 <math.h> */

/****************************************************************************
* 函數名：  Judge_PrimeNumber
* 功能描述：判斷一個數是否為質數
* 輸入引數：
*			_number：需要判斷的數
* 返回值：
*			1：是質數
*			0：不是質數
* 外部引數：無
* 注意事項：無
*
* 作者：	樑國慶
* 日期：	2021-12-11
* 修改記錄：
****************************************************************************/
int Judge_PrimeNumber(int _number)
{
    int i = 0;

    if (_number < 2)
    {
        return 0;   /* 需要判斷的數小於 2，則不是質數，返回 0 */
    }

    for (i = 2; i <= sqrt(_number); i++)    /* 遍歷從 2 到 √_number 區間中的所有數 */
    {
        if (_number % i == 0)
        {
            return 0;                       /* 若可以被整除，則不是質數，返回 0 */
        }
    }

    return 1;       /* 若執行完以上程式均未返回，則是指數，返回 1 */
}

int main()
{
    int i = 0, num = 0;

    for (i = 101; i <= 200; i += 2)        /* 遍歷 101 至 200 之間的數 */
    {
        if (Judge_PrimeNumber(i) == 1)  /* 呼叫判斷質數的函數，判斷輸入的整數 i */
        {
            num++;

            printf("%d.\t", num);       /* 輸出當前質數的個數 */
            printf("%d\n", i);          /* 輸出質數 */
        }
    }

    return 0;
}