使用c语言使用较快的方法输出1 到N 间的素数。
时间: 2024-01-22 07:18:53 浏览: 58
以下是使用 C 语言的筛选法实现输出 1 到 N 间的素数的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
void printPrimes(int n);
int main()
{
int n;
printf("Enter the value of n: ");
scanf("%d", &n);
printPrimes(n);
return 0;
}
void printPrimes(int n)
{
bool* isPrime = (bool*)malloc((n + 1) * sizeof(bool));
// Initialize all elements to true
for (int i = 2; i <= n; i++)
{
isPrime[i] = true;
}
// Apply the sieve of Eratosthenes
for (int i = 2; i <= sqrt(n); i++)
{
if (isPrime[i])
{
for (int j = i * i; j <= n; j += i)
{
isPrime[j] = false;
}
}
}
// Print the primes
for (int i = 2; i <= n; i++)
{
if (isPrime[i])
{
printf("%d ", i);
}
}
free(isPrime); // Free the memory allocated to isPrime
}
```
该代码首先通过 malloc 函数动态分配了一个大小为 (n+1) 的 bool 类型数组 isPrime,数组的下标表示对应的数字是否为素数(true 表示是素数,false 表示不是素数)。接着,将数组的所有元素都初始化为 true。然后,利用 Eratosthenes 筛法(Sieve of Eratosthenes)找出素数,最后输出这些素数。
在 Eratosthenes 筛法中,从 2 开始,将所有能被 2 整除的数标记为非素数,再找到下一个未标记的数(即 3),将所有能被 3 整除的数标记为非素数,以此类推,直到找到所有小于等于 n 的素数。由于每个合数都至少有一个小于它的质因数,所以只需要考虑小于等于 sqrt(n) 的质数作为筛子。
该算法的时间复杂度为 O(nloglogn),空间复杂度为 O(n)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)