首页 > 编程笔记 > C语言笔记

C语言判断素数的3种方法(附带源码)

素数在数学中具有特殊的地位,它们是只有两个正因数(1和自身)的自然数。素数在密码学、计算机科学和数论中有着广泛的应用。

首先要先明白素数的定义:除了 1 和本身之外,没有其他的因数的数,即不能被其他数整除。

同时要注意,1不是素数。

以下是用C语言判断素数的 3 种方法,并附带了源码和注释。

1. 循环判断法

在这种方法中,我们从 2 开始,一直到输入的数字 i,逐步检查是否有任何数字能整除 i:
C语言代码如下:
#include<stdio.h>
int main()
{
    int i, m;
    printf("请输入一个大于1的整数:");
    scanf("%d", &i);

    for (m = 2; m <= i; m++){
        if (i % m == 0){  //当2-m之间遇到因数时,结束循环
            break;
        }
    }
    if (m == i){  //如果遇到的因数就是它本身,是素数
        printf("%d是素数", i);
    }else{
        printf("%d不是素数", i);
    }

    return 0;
}

2. 因数计数法

此方法通过统计一个数字的因数数量来判断其是否为素数。初始化一个计数器 count,然后从 1 遍历到输入的数字 i,每找到一个因数,计数器就增加。如果最终计数器的值为 2,那么 i 就是一个素数。

C语言代码如下:
#include<stdio.h>
int main()
{
    int i, m;
    int count = 0;
    printf("请输入一个大于1的整数:\n");
    scanf("%d", &i);

    for (m = 1; m <= i; m++){
        if (i % m == 0){  //统计要判断的数的因数个数
            count++;
        }
    }
    if (count == 2){  //如果只有2个因数
        printf("%d是素数", i);
    }else{
        printf("%d不是素数", i);
    }

    return 0;
}

3. 平方根优化法

利用数学中的平方根概念,这种方法通过计算输入数字 n 的平方根 m,并只检查从 2 到 m 的整数是否能整除 n。

这种方法的优势在于,它减少了不必要的循环迭代,因为如果 n 不是素数,它必定有一个因数小于或等于其平方根。

此代码中引用了求平方根 sqrt() 函数,所以要引用 math.h。

C语言代码如下:
#include<stdio.h>
#include<math.h>  //求平方根需要引用
int main()
{
    int n, m, i;  //定义需要用到的变量
    printf("请输入一个大于1的正整数:");
    scanf("%d", &n);  //输入要判断的数

    m = sqrt(n);  //求输入数的平方根
    for (i = 2; i <= m; i++){  //取2-m之间的每一个整数
        if (n % i == 0){  //判断能否整除n
            break;  //非素数,跳出循环
        }
    }
    if (i > m){
        printf("%d是素数!\n", n);  //循环正常结束,是素数
    }else{
        printf("%d不是素数!\n", n);  //循环中途退出,不是素数
    }

    return 0;
}

补充说明

素数的分布是不规则的,但通常在自然数中,随着数值的增大,素数的密度逐渐减小。

声明:《C语言系列教程》为本站“54笨鸟”官方原创,由国家机构和地方版权局所签发的权威证书所保护。