使用较快的方法输出1 到N 间的素数。 输入格式: 输入一个正整数n。(1<n<=1000000) 输出格式: 输出小于等于n的所有素数,每个素数以空格隔开 用c语言完成
时间: 2024-03-10 10:48:21 浏览: 28
以下是使用埃氏筛法(Eratosthenes sieve)的C语言代码实现:
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
void find_primes(int n) {
bool *is_prime = (bool*) malloc((n+1) * sizeof(bool)); // 动态分配数组空间
int i, j;
for (i = 2; i <= n; i++) {
is_prime[i] = true; // 初始化数组
}
int limit = sqrt(n);
for (i = 2; i <= limit; i++) {
if (is_prime[i]) {
for (j = i * i; j <= n; j += i) {
is_prime[j] = false; // 将i的倍数标记为合数
}
}
}
for (i = 2; i <= n; i++) {
if (is_prime[i]) {
printf("%d ", i); // 输出素数
}
}
free(is_prime);
}
int main() {
int n;
scanf("%d", &n);
find_primes(n);
return 0;
}
```
该程序首先使用动态分配数组的方式初始化一个大小为 n+1 的布尔类型数组,初始值全部设为 true。根据素数的定义,我们只需要从 2 开始枚举到 sqrt(n)(即 n 的平方根)即可,因为若一个数 i 不是素数,则它一定可以分解成 i = p * q 的形式,其中 p 和 q 都是小于 i 的数,因此至少有一个数小于等于 sqrt(i)。对于每个素数 i,我们将其所有的倍数都标记为合数,这样就可以筛选出所有的素数。最后再遍历一次数组,输出所有标记为 true 的位置对应的数即可。
该算法的时间复杂度是 O(nloglogn),空间复杂度是 O(n)。因此,在 n 较大时,该算法的效率更高。