c语言怎么筛选素数-C++-PHP中文网

c语言怎么筛选素数

下次还敢

发布： 2024-05-26 04:03:22

原创

1133人浏览过

C语言中筛选素数的方法是使用埃拉托斯特尼筛法，其步骤如下：创建一个长度为 n+1 的布尔数组 sieve[]，初始化 sieve[0] 和 sieve[1] 为 false，其他元素为 true。从 i = 2 开始，若 sieve[i] 为 true，则 i 是素数，并将其倍数 sieve[j] 设置为 false，其中 j 从 i*i 到 n，步长为 i。遍历 sieve[] 数组，输出 sieve[i] 为 true 的所有索引 i。

c语言怎么筛选素数

C 语言中筛选素数的方法

在 C 语言中，筛选素数可以使用埃拉托斯特尼筛法。这种算法通过以下步骤工作：

创建布尔数组：创建一个长度为 n+1 的布尔数组 sieve[]，其中 n 是筛选的最大整数。
初始化数组：将 sieve[0] 和 sieve[1] 设置为 false，因为 0 和 1 不是素数。将所有其他元素初始化为 true。
筛除非素数：从 i = 2 开始，对于每个 i，如果 sieve[i] 为 true，那么 i 是一个素数。对于 j = i*i 到 n 步长为 i，将 sieve[j] 设置为 false，因为它们都是 i 的倍数，因此不是素数。
输出素数：遍历数组 sieve[] 并输出 sieve[i] 为 true 的所有索引 i。

以下是一个 C 语言实现埃拉托斯特尼筛法的示例代码：

析稿Ai写作

科研人的高效工具：AI论文自动生成，十分钟万字，无限大纲规划写作思路。

142

查看详情

<code class="c">#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

void sieve_of_eratosthenes(int n) {
  bool *sieve = (bool *)malloc((n + 1) * sizeof(bool));

  for (int i = 0; i <= n; i++) {
    sieve[i] = true;
  }

  sieve[0] = sieve[1] = false;

  for (int i = 2; i <= n; i++) {
    if (sieve[i] == true) {
      for (int j = i * i; j <= n; j += i) {
        sieve[j] = false;
      }
    }
  }

  printf("Prime numbers up to %d:\n", n);
  for (int i = 2; i <= n; i++) {
    if (sieve[i] == true) {
      printf("%d ", i);
    }
  }
  printf("\n");

  free(sieve);
}

int main() {
  int n;
  printf("Enter the maximum integer: ");
  scanf("%d", &n);
  sieve_of_eratosthenes(n);
  return 0;
}</code>

登录后复制

这个代码将提示用户输入要筛选的整数 n，然后打印出所有小于或等于 n 的素数。

立即学习“C语言免费学习笔记（深入）”；

以上就是c语言怎么筛选素数的详细内容，更多请关注php中文网其它相关文章！