C 语言程序：采用先进算法快速识别素数 (c语言程序设计)

文章编号：17555 / 分类：最新资讯 / 更新时间：2024-07-07 13:55:12 / 浏览：次

在计算机科学中，素数是一个非常重要的概念。素数指只能被 1 和自身整除的正整数，而不能被其他任何正整数整除。素数在密码学、数据安全和科学计算等众多领域都有广泛的应用。

识别素数是一个经典的算法问题。有很多算法可以解决这个问题，但其中最著名和最有效的方法之一是埃拉托斯特尼筛法。

埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种基于筛除法的算法，用于识别素数。其基本原理是：从 2 开始，逐一检查每个正整数，如果当前整数是素数，则将该整数所有倍数标记为非素数；如果当前整数不是素数，则跳过该整数继续检查下一个整数。

以下是埃拉托斯特尼筛法的算法步骤：

创建一个长度为 n+1 的布尔数组，其中 n 是要检查的正整数的上限。
将数组中所有元素初始化为 True，表示它们都是潜在的素数。
从 2 开始，逐一检查每个正整数 i：
如果 i 是 True，则 i 是素数：
将 i 的所有倍数标记为 False，即逐个将 i2, i3, i4, ... 标记为 False。
如果 i 不是 True，则跳过该整数。
重复步骤 3，直到检查完所有正整数。

C 语言程序

以下是用 C 语言编写的埃拉托斯特尼筛法的程序：

cinclude include int main() {int n;printf("请输入要检查的正整数的上限：");scanf("%d", &n);// 创建布尔数组int isPrime = (int )malloc((n + 1) sizeof(int));if (isPrime == NULL) {printf("内存分配失败！\n");return 1;}// 初始化数组for (int i = 0; i <= n; i++) {isPrime[i] = 1;}// 应用埃拉托斯特尼筛法for (int i = 2; i <= n; i++) {if (isPrime[i]) {for (int j = i i; j <= n; j += i) {isPrime[j] = 0;}}}// 打印素数printf("素数：");for (int i = 2; i <= n; i++) {if (isPrime[i]) {printf(" %d", i);}}printf("\n");// 释放内存free(isPrime);return 0;}```