如何在C语言中输出素数 |21xrx.com

如何在C语言中输出素数

2023-06-18 21:14:07 深夜i -- --

C语言素数输出

C语言是一种广泛使用的编程语言，可以使用它来解决许多数学问题，如查找素数。素数是只能被1和它本身整除的正整数。在本文中，我们将讨论如何在C语言中输出素数。

有很多方法可以找出素数，这里将介绍三种方法：暴力枚举、埃氏筛法和欧拉筛法。暴力枚举是最简单的方法，但对于较大的数会比较耗时，而埃氏筛法和欧拉筛法则可以更高效地找出素数。

使用暴力枚举法，我们可以从2开始遍历每个数，判断它是否是素数。具体实现代码如下：


#include 
int main() {
  int n;
  printf("请输入一个正整数n：");
  scanf("%d", &n);
  for (int i = 2; i <= n; i++) {
    int flag = 1; // flag为1表示i是素数，为0则表示不是
    for (int j = 2; j < i; j++) {
      if (i % j == 0) // 如果i能被j整除
    }
    if (flag == 1) {
      printf("%d ", i); // 输出i
    }
  }
  return 0;
}

接下来我们介绍埃氏筛法。该方法先将所有数字标记为素数，然后从2开始遍历，如果某个数为素数，则将它的倍数标记为合数。具体实现代码如下：


#include 
int main() {
  int n;
  printf("请输入一个正整数n：");
  scanf("%d", &n);
  int is_prime[100000]; // 标记数组，is_prime[i]为1表示i是素数，为0表示不是
  for (int i = 0; i < n + 1; i++) {
    is_prime[i] = 1; // 先默认全是素数
  }
  for (int i = 2; i <= n; i++) {
    if (is_prime[i] == 1) { // 如果i是素数
      printf("%d ", i); // 输出i
      for (int j = i * i; j <= n; j += i) {
        is_prime[j] = 0; // 将i的倍数标记成合数
      }
    }
  }
  return 0;
}

最后我们介绍欧拉筛法，该方法结合了前两种方法的优点，是找素数的最优解。具体实现代码如下：


#include 
int main() {
  int n;
  printf("请输入一个正整数n：");
  scanf("%d", &n);
  int is_prime[100000]; // 标记数组，is_prime[i]为1表示i是素数，为0表示不是
  int primes[100000]; // 存放素数的数组，primes[i]存放第i个素数
  int prime_count = 0; // 当前已经找到的素数个数
  for (int i = 2; i <= n; i++) {
    if (is_prime[i] == 0) 则直接跳过
      continue;
    
    primes[prime_count++] = i; // 将i添加到素数列表中
    for (int j = 0; j < prime_count; j++) {
      if (i * primes[j] > n) { // 如果i和primes[j]的乘积超过了n，则剩下的数字都不用再筛一遍
        break;
      }
      is_prime[i * primes[j]] = 0; // 将i和primes[j]的乘积标记为合数
      if (i % primes[j] == 0) { // 如果i能整除primes[j]，则后面的数字都不用再筛一遍
        break;
      }
    }
  }
  for (int i = 0; i < prime_count; i++) {
    printf("%d ", primes[i]); // 输出所有素数
  }
  return 0;
}

上一篇: idea打包java可执行jar包

下一篇: Java中的字符串和字符

评论区

()

相似文章