一文解决如何使用 C 语言判断质数(素数)[ 附解析与源码 ]

时间:2023-01-21 22:09:27

前言

质数历来都是数学界的宠儿,是数学里神秘的谜团。

质数又和 C 语言有着不解之缘,本篇文章将讲解如何用 C 语言判断质数。

为了方便大家在读完此文章后使用文中程序,我会将判断质数的程序封装成函数,此函数的功能是:判断形参 _number 是否是质数,若 _number 是质数,则返回 1;若不是质数,则返回 0

何为质数

质数又称素数。一个大于 1 的自然数,除了 1 和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数(规定 1 既不是质数也不是合数)。

C 语言判断质数

在了解了质数的定义后,现在我们便可以着手编写程序啦。

现在给定一个正整数 number,要求我们判断此数是否为质数。针对这一要求本篇采用两种判断方法,分别是:暴力求解 与 巧用平方根。

暴力求解

通过质数的定义可以得到如何判断一个数是否为质数, 我们可以通过遍历从 2number - 1 这个区间中的所有数,如果都不能被 number 整除,则 number 是质数,否则 number 不是质数。

具体代码如下:

/****************************************************************************
* 函数名:  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 < _number; i++)   /* 遍历从 2 到 _number - 1 区间中的所有数 */
    {
        if (_number % i == 0)
        {
            return 0;               /* 若可以被整除,则不是质数,返回 0 */
        }
    }

    return 1;       /* 若执行完以上程序均未返回,则是指数,返回 1 */
}

巧用平方根

使用暴力求解固然可以求出一个数是否为质数,但运算次数是最多的,运行速度也是最慢的,我们还可以将程序进行优化,提升程序运行时的效率。

在一般领域,对正整数 number,如果用 2 到 $\sqrt{number}$ 之间的所有整数去除,均无法整除,则 number 为质数。那么就可以利用这一方法,巧用平方根判断一个数是否为质数。

在 C 语言中求平方根可以使用 C 标准库,<math.h> 头文件中定义了各种数学函数,sqrt() 函数是平方根函数,功能是计算一个非负实数的平方根,调用时程序要包含 <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 */
}

如何调用函数

对于如何使用 C 语言判断质数,共讲解了两种方法并分别将编写的程序封装成为函数,现在我们来讲解一下如何在实际应用中调用它们。

在这里,我以巧用平方根为例进行讲解(暴力求解的调用方法与之相同),也特别推荐大家在以后的使用中优先选择巧用平方根这种方法,因为通过平方根进行判断是运算次数最少的,可以极大的提高我们程序的效率。

样例代码中,我们输入一个整数,然后调用判断质数的函数,若输入的数是质数则输出 Yes,否则输出 No

具体代码如下:

#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 N = 0;

    scanf("%d", &N);

    if (Judge_PrimeNumber(N) == 1)  /* 调用判断质数的函数,判断输入的整数 N */
    {
        printf("Yes\n");            /* 是质数,则输出 Yes */
    }
    else
    {
        printf("No\n");             /* 否则输出 No */
    }

    return 0;
}

后记

至此,我们讲解了关于质数的定义,带领大家编写了 C 语言判断质数的程序代码,并将所写代码封装成为函数,同时为大家演示了如何调用函数来判断质数。
相信看完本篇文章的你,以后再遇到 C 语言判断质数的问题,可以解决的游刃有余。