编写程序实现用Eratosthenes筛法寻找给定范围内的素数C++代码及运行结果
时间: 2024-09-10 16:27:44 浏览: 27
Eratosthenes筛法是一种古老的求解一定范围内所有素数的经典算法。以下是用C++编写的一个简单版本:
```cpp
#include <iostream>
#include <vector>
void sieveOfEratosthenes(int n) {
std::vector<bool> primes(n+1, true); // 初始化一个布尔数组, 2; i * i <= n; i++) { // 只需要检查到√n
if (primes[i]) { // 如果i是质数
for (int j = i * i; j <= n; j += i) { // 将i的所有倍数标记为合数
primes[j] = false;
}
}
}
// 打印出所有素数
for (int i = 2; i <= n; i++)
if (primes[i])
std::cout << i << " ";
}
int main() {
int range = 50; // 示例范围,你可以替换为你想要查找素数的上限
sieveOfEratosthenes(range);
return 0;
}
```
运行此程序,假设输入范围为50,输出将会是2、3、5、7、11、13、17、19、23、29、31、37、41、43、47,这些都是50以内的素数。
相关问题
编写程序实现用Eratosthenes筛法寻找给定范围内的素数代码及运行结果
埃拉托斯特尼筛法是一种古老的算法,用于找出一定范围内所有质数。它通过不断排除能被已知质数整除的数,逐步筛选出所有的素数。以下是使用Python语言实现的一个简单版本:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n+1)
primes[0], primes[1] = False, False # 0和1不是质数
for i in range(2, int(n**0.5) + 1):
if primes[i]:
for j in range(i*i, n+1, i): # 只需要检查i的倍数
primes[j] = False
return [i for i, is_prime in enumerate(primes) if is_prime]
# 示例:找到1到30内的素数
result = sieve_of_eratosthenes(30)
print(f"1到30之间的素数有:{result}")
编写程序实现用Eratosthenes筛法寻找给定范围内的素数代码及结果
当然可以。Eratosthenes筛法是一种古老的算法,用于查找一定范围内所有的质数(素数是指只有1和它本身两个正因数的自然数)。以下是使用Python编写的一个简单版本的埃拉托斯特尼筛法:
```python
def eratosthenes_sieve(n):
# 创建一个布尔列表,初始所有数字都标记为True,表示它们可能是素数
primes = [True] * (n + 1)
primes[0] = primes[1] = False # 0和1不是素数
# 遍历到√n,将每个素数的倍数标记为合数
for i in range(2, int(n**0.5) + 1):
if primes[i]:
for j in range(i*i, n+1, i): # 跳过i的平方,因为之前的因子已经被标记了
primes[j] = False
# 输出所有小于等于n的素数
prime_numbers = [i for i, is_prime in enumerate(primes) if is_prime]
return prime_numbers
# 示例,找出1到30之间的素数
result = eratosthenes_sieve(30)
print("1到30内的素数有:", result)
```
当你运行这段代码,会得到1到30内的所有素数:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]。