求n以内(包括n)的素数。(n<=100000)
时间: 2023-04-26 12:01:30 浏览: 73
这是一个求解质数的问题,可以使用筛法求解。具体步骤如下:
1. 创建一个长度为n+1的布尔数组,用来标记每个数是否为质数,初始值都为true。
2. 从2开始,将2的倍数(除2以外)标记为false,因为它们不是质数。
3. 从3开始,将3的倍数(除3以外)标记为false,因为它们不是质数。
4. 依次类推,对于每个未被标记为false的数i,将i的倍数(除i以外)标记为false。
5. 最后,所有未被标记为false的数就是小于等于n的质数。
代码实现如下:
```python
def find_primes(n):
is_prime = [True] * (n+1)
is_prime[] = is_prime[1] = False
for i in range(2, int(n**.5)+1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
primes = [i for i in range(n+1) if is_prime[i]]
return primes
```
调用该函数即可得到小于等于n的所有质数。
相关问题
求N以内(包括N)的素数。(N<= 100000)
可以使用筛法求解,时间复杂度为O(NloglogN)。
以下是代码:
```
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 5;
bool isPrime[MAXN];
int main() {
int n;
cin >> n;
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
for (int j = i * 2; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
```
用筛法求N之内的素数。(1<=N<=10000000)
好的,这是一个经典的算法问题。我们可以使用埃拉托色尼筛法(Sieve of Eratosthenes)来解决这个问题。
具体步骤如下:
1. 先创建一个长度为N+1的数组,用来记录每个数字是否是素数,初始值都为true。
2. 从2开始,将2的倍数(除2以外)都标记为false,因为它们不是素数。
3. 找到下一个未标记为false的数字p,将p的倍数(除p以外)都标记为false。
4. 重复步骤3,直到p²>N。
5. 遍历数组,输出所有标记为true的数字,即为N以内的素数。
以下是Python代码实现:
```python
def sieve_of_eratosthenes(n):
is_prime = [True] * (n+1)
is_prime[0], is_prime[1] = False, False
p = 2
while p**2 <= n:
if is_prime[p]:
for i in range(p**2, n+1, p):
is_prime[i] = False
p += 1
primes = [i for i in range(n+1) if is_prime[i]]
return primes
```
调用`sieve_of_eratosthenes(N)`即可得到N以内的素数列表。
相关推荐
![](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)