首页C实现欧拉筛n到m的素数

C实现欧拉筛n到m的素数

时间: 2024-12-18 18:15:41 浏览: 84

在C语言中，实现欧拉筛法(Euler's Sieve)来找出从n到m之间的所有素数，可以按照以下步骤进行： 1. **创建布尔数组**：初始化一个大小为(m+1)的布尔数组isPrime[]，所有的值都设为true，表示开始时假设每个数都是素数。 2. **处理小于等于sqrt(m)的素数**：从2开始，遍历到√m（向下取整）。对于每个素数p，将isPrime[p]设为false，并标记它的所有倍数（即p*p到m的所有整数）为合数，因为它们有共同因子p。 3. **筛过当前的素数后**，继续寻找下一个未被标记为合数的数，这个数就是新的素数。 4. **生成结果列表**：最后，将isPrime数组中索引位置对应的值为true的元素，对应的就是区间[n, m]内的素数。以下是简化后的C代码示例： ```c #include <stdio.h> #include <math.h> void sieve(int n, int m) { int limit = sqrt(m) + 1; int* isPrime = (int*)malloc((m + 1) * sizeof(int)); for (int i = 0; i <= m; i++) { isPrime[i] = 1; } for (int p = 2; p <= limit; p++) { if (isPrime[p]) { for (int j = p * p; j <= m; j += p) { isPrime[j] = 0; } } } printf("Prime numbers from %d to %d are:\n", n, m); for (int i = n; i <= m; i++) { if (isPrime[i]) { printf("%d ", i); } } free(isPrime); } int main() { int n = 50, m = 100; sieve(n, m); return 0; } ```

阅读全文