首页c语言输出N以内的所有素数

c语言输出N以内的所有素数

时间: 2024-12-06 22:24:33 浏览: 79

在C语言中，输出N以内的所有素数，你可以通过使用“埃拉托斯特尼筛法”（Sieve of Eratosthenes）来实现。这个算法的基本思想是从2开始，将每个数的倍数标记为合数，直到遍历到sqrt(N)，因为大于 sqrt(N) 的因数已经在小于它的平方数那里被标记过了。以下是简单的C代码实现： ```c #include <stdio.h> #include <stdbool.h> #define MAX_N 100 // 判断是否为素数 bool isPrime(int num) { if (num <= 1) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true; } // 输出N以内的素数 void printPrimes(int n) { bool prime[MAX_N + 1] = {true}; // 初始化所有数为素数 for (int p = 2; p * p <= n; p++) { if (prime[p]) { for (int i = p * p; i <= n; i += p) prime[i] = false; // 标记p的倍数为合数 } } printf("素数有："); for (int p = 2; p <= n; p++) if (prime[p]) printf("%d ", p); printf("\n"); } int main() { int N; printf("请输入一个整数N："); scanf("%d", &N); printPrimes(N); return 0; } ``` 在这个代码中，`isPrime` 函数用于检查一个数是否为素数，`printPrimes` 函数则应用埃拉托斯特尼筛法找出并打印出N以内的所有素数。

阅读全文