c语言怎么表现素数-C++-PHP中文网

c语言怎么表现素数

下次还敢

发布： 2024-05-26 03:51:24

原创

1261人浏览过

在 C 语言中寻找素数有两种方法：从 2 到根号 n 遍历，检查数字是否能被比它小的数字整除。使用埃拉托斯特尼筛法，标记所有非素数，未标记的数字即为素数。

c语言怎么表现素数

C 语言中寻找素数的方法

素数是一个只能被 1 和它本身整除的正整数。在 C 语言中，有多种方法可以找出素数。

方法 1：从 2 到根号 n 遍历

最直接的方法是从 2 到数字 n 的平方根遍历。对于每个数字 i，我们检查它是否能被比它小的任何数字整除。如果没有，则它是素数。

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

Krikey AI

查看详情

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

int is_prime(int n) {
  if (n < 2) {
    return 0;  // 1 和 1 以下的数字不是素数
  }
  for (int i = 2; i <= n / i; i++) {
    if (n % i == 0) {
      return 0;  // 找到了一个因子，因此不是素数
    }
  }
  return 1;  // 没有找到因子，因此是素数
}

int main() {
  int number;
  printf("输入一个数字：");
  scanf("%d", &number);
  if (is_prime(number)) {
    printf("%d 是素数。\n", number);
  } else {
    printf("%d 不是素数。\n", number);
  }
  return 0;
}</code>

登录后复制

方法 2：埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种更有效的方法，可以找到给定范围内的所有素数。

该算法从一个包含所有数字的数组开始。然后，它从 2 开始，并标记数组中的所有 2 的倍数。然后，它从 3 开始，并标记数组中所有 3 的倍数，但不包括 2 的倍数。此过程一直持续到给定范围内的最高数字。

最后，数组中未被标记的数字是素数。

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

int main() {
  int n;
  printf("输入要查找素数的范围上限：");
  scanf("%d", &n);

  // 创建一个包含所有数字的数组
  int *numbers = (int *)malloc(sizeof(int) * (n + 1));
  for (int i = 0; i <= n; i++) {
    numbers[i] = 1;
  }

  // 标记非素数
  for (int i = 2; i <= n; i++) {
    if (numbers[i]) {  // 如果 i 是素数
      for (int j = i * i; j <= n; j += i) {
        numbers[j] = 0;  // 标记 i 的所有倍数
      }
    }
  }

  // 打印素数
  printf("素数：");
  for (int i = 2; i <= n; i++) {
    if (numbers[i]) {
      printf("%d ", i);
    }
  }
  printf("\n");

  free(numbers);
  return 0;
}</code>

登录后复制

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