pta7-294筛法求素数
时间: 2023-11-01 14:07:32 浏览: 93
pta7-294题要求使用筛法求出1~N以内的质数。素数筛法是一种高效的求解质数的算法,理论复杂度小于O(sqrt(n)),在因子远小于n的情况下能达到最佳效果。具体实现方法是从2开始,将每个质数的倍数都标记成合数,直到筛完所有小于等于N的数。最后剩下的未被标记的数即为质数。虽然算法相对复杂,但是在大数区间 [10^8,10^9] 内随机选取的平均运算时间是开方法 ≈ 2: 1。函数接口定义为:vector sieve(int n); //函数声明,求n以内的质数。
相关问题
数组-筛法求素数
好的,我可以为您解答关于数组-筛法求素数的问题。
筛法求素数,也称为埃氏筛法,是一种非常高效的求解素数的方法。
其基本思想是:先用一个数组来表示从2到N的所有自然数,假设这个数组为prime[N+1],初始时,将prime[2]~prime[N]赋值为1,表示这些数都是素数。
然后从2开始,依次将2的倍数、3的倍数、4的倍数……以此类推,都标记为合数。具体实现时,可以使用两个循环嵌套,外层循环枚举2~N之间的所有自然数,内层循环枚举当前数的所有倍数,将它们标记为合数,即将prime[i]的倍数prime[i*j]置为0。
最后,所有值为1的prime[i]都是素数。
下面是一个简单的C++代码实现:
```c++
const int N = 1000000;
int prime[N+1]; // 用来存储素数的数组
void sieve(int n) {
memset(prime, 1, sizeof(prime)); // 初始化为1,表示都是素数
prime[0] = prime[1] = 0; // 0和1不是素数
for(int i=2; i<=n; i++) {
if(prime[i]) { // 如果是素数
for(int j=2; i*j<=n; j++) {
prime[i*j] = 0; // 将i的倍数标记为合数
}
}
}
}
```
这个算法的时间复杂度为O(NloglogN),非常适用于N比较大的情况。
埃氏筛法求1-n的素数
埃氏筛法是一种用于求解素数的算法,它的基本思想是从小到大遍历每个数,将其所有的倍数标记为合数,最终剩下的未被标记的数即为素数。
具体步骤如下:
1. 创建一个长度为n+1的布尔数组isPrime,并将所有元素初始化为true。
2. 将isPrime和isPrime设置为false,因为0和1不是素数。
3. 从2开始遍历到n,如果isPrime[i]为true,则将i的所有倍数(除了i本身)都标记为false,即isPrime[j * i] = false,其中j >= 2。
4. 遍历完所有数后,isPrime中值为true的下标即为素数。
以下是埃氏筛法求解1-n的素数的示例代码:
```python
def sieve_of_eratosthenes(n):
isPrime = [True] * (n + 1)
isPrime[0] = isPrime[1] = False
for i in range(2, int(n**0.5) + 1):
if isPrime[i]:
for j in range(i * i, n + 1, i):
isPrime[j] = False
primes = []
for i in range(2, n + 1):
if isPrime[i]:
primes.append(i)
return primes
n = 100
primes = sieve_of_eratosthenes(n)
print(primes)
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)