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

C语言for循环判断素数（附带源码和解析）

素数，也称为质数，是一个大于 1 的自然数，除了 1 和它本身外，不能被其他自然数整除。换句话说，素数只有两个因子：1 和它自身。例如，2、3、5、7、11 和 13 都是素数。


素数在数学和计算机科学中扮演着重要角色，尤其在密码学和数据加密领域广泛应用。


要判断一个数是否为素数，我们需要检查它是否能被除了 1 和自身之外的任何数整除。如果找到了这样的数，那么它就不是素数。反之，如果除了 1 和自身外没有其他因子，那么它就是素数。
 

在C语言中，我们可以使用 for 循环来实现素数的判断，这种方法的基本原理是：对于给定的数 n，我们只需要检查从 2 到 n 的所有整数是否能整除 n。
 

为什么只需要检查到 n 呢？这是因为如果 n 不是素数，它必定有一个小于或等于 n 的因子。这个优化可以显著减少循环的次数，提高程序的效率。


下面是一个使用 C 语言实现的判断素数的函数：

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
    if (n <= 1) return false;  // 1 和负数不是素数
    if (n == 2) return true;   // 2 是最小的素数
    if (n % 2 == 0) return false;  // 偶数（除了2）都不是素数

    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num;
    printf("请输入一个正整数：");
    scanf("%d", &num);

    if (isPrime(num)) {
        printf("%d 是素数\n", num);
    } else {
        printf("%d 不是素数\n", num);
    }

    return 0;
}

让我们详细解析这段代码：

isPrime 函数接受一个整数参数 n，并返回一个布尔值，表示 n 是否为素数。函数首先进行了一些快速检查：

接下来，函数使用 for 循环从 3 开始，以步长 2 递增（跳过偶数），一直检查到 n。在每次循环中，如果 n 能被 i 整除，就说明 n 不是素数，函数立即返回 false。如果循环结束后没有找到因子，函数返回 true，表示 n 是素数。
 

在 main 函数中，我们提示用户输入一个正整数，然后调用 isPrime 函数判断这个数是否为素数，并打印结果。
 

这个程序的时间复杂度是 O(n)，相比于检查到 n-1 的朴素算法 O(n)，效率有了显著提升。然而，对于非常大的数，这种方法仍然可能比较慢。在实际应用中，对于更大范围的素数判断，我们通常会使用更高效的算法，如 Miller-Rabin 素性测试等概率算法。
 

使用这个程序，我们可以轻松判断一个数是否为素数。让我们测试一些数：

请输入一个正整数：17
17 是素数

请输入一个正整数：24
24 不是素数

请输入一个正整数：97
97 是素数

通过这个程序，我们不仅可以判断单个数是否为素数，还可以通过简单的修改来找出一定范围内的所有素数。例如，我们可以在 main 函数中添加一个循环，遍历从 2 到 100 的所有数，并打印出其中的素数：

int main() {
    printf("2到100之间的素数有：\n");
    for (int i = 2; i <= 100; i++) {
        if (isPrime(i)) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

这段代码会输出：

2到100之间的素数有：
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

通过这个例子，我们可以看到C语言 for 循环在解决实际问题中的应用，它不仅可以用于判断单个数是否为素数，还可以用于生成素数表。

相关文章