C 语言输出100至200之间的质数(素数)

时间:2023-01-29 07:12:22

题目描述

运行 C 程序,输出 100 至 200 之间的质数。

输入描述

输出描述

输出 100 至 200 之间的质数,每行输出一个质数,每个质数前面需要带有序号。

输出样例

C 语言输出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;
}