首页用C语言写出欧拉筛的代码

用C语言写出欧拉筛的代码

时间: 2024-12-04 10:15:15 浏览: 118

好的,我很乐意为您介绍欧拉筛算法并提供C语言的实现代码。欧拉筛(Euler's Sieve)是一种高效的素数筛选算法,用于生成一定范围内的所有素数。它的时间复杂度为O(n),空间复杂度为O(n),是已知最快速的素数筛选算法之一。以下是欧拉筛的C语言实现代码: ```c #include <stdio.h> #include <stdbool.h> #include <stdlib.h> #define MAX 1000000 bool isPrime[MAX + 1]; int primes[MAX / 10]; int primeCount = 0; void eulerSieve(int n) { for (int i = 2; i <= n; i++) { if (!isPrime[i]) { primes[primeCount++] = i; } for (int j = 0; j < primeCount && i * primes[j] <= n; j++) { isPrime[i * primes[j]] = true; if (i % primes[j] == 0) { break; } } } } int main() { int n; printf("请输入要筛选的范围: "); scanf("%d", &n); eulerSieve(n); printf("素数数量: %d\n", primeCount); printf("素数列表: "); for (int i = 0; i < primeCount; i++) { printf("%d ", primes[i]); } printf("\n"); return 0; } ``` 这个实现的主要步骤如下: 1. 初始化: 将所有数的isPrime值设为false,表示最初假设所有数都是素数。 2. 从2开始遍历到n,对于每个数: - 如果isPrime[i]为false,说明i是素数,将其加入primes数组。 - 对于当前素数primes[j],将i * primes[j]标记为非素数。 - 如果i能被primes[j]整除,停止当前循环,因为后续的数会被更大的素数筛掉。 3. 最后,primes数组中就包含了所有的素数。欧拉筛的主要优点是它在筛选过程中避免了重复的乘法操作,每个合数只被标记一次,因此效率非常高。

阅读全文