埃式筛选法求质数 请编写函数getPrimes(N) 使用埃式筛选法打印前N个质数。 注意:公共变量的使用,可减少函数多次调用产生的重复计算问题
时间: 2023-07-15 13:14:08 浏览: 87
以下是使用埃式筛选法求质数的 Python 代码:
```python
def getPrimes(N):
is_prime = [True] * (N+1) # 创建一个布尔数组,表示该下标对应的数是否为质数
is_prime[0] = is_prime[1] = False # 0和1不是质数
for i in range(2, int(N ** 0.5)+1):
if is_prime[i]:
for j in range(i*i, N+1, i):
is_prime[j] = False # 将i的倍数标记为非质数
primes = []
for i in range(2, N+1):
if is_prime[i]:
primes.append(i)
return primes
```
这个函数根据输入的整数 N,返回前 N 个质数的列表。使用埃式筛选法,先将 0 和 1 标记为非质数,然后从 2 开始循环,将其倍数标记为非质数。最后遍历整个数组,将所有标记为质数的数加入结果列表中。
相关问题
筛选法求质数 编写程序,输入一个大于2的自然数,输出小于该数字的所有质数组成的列表
筛选法,也称为埃拉托斯特尼筛法(Sieve of Eratosthenes),是一种古老的算法,用于找出一定范围内所有质数。它的基本思想是从2开始,将每个质数的倍数标记为合数,直到达到给定的界限。以下是使用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]: # 如果i是质数
for j in range(i*i, n+1, i): # 将i的倍数标记为合数
primes[j] = False
prime_list = [i for i, is_prime in enumerate(primes) if is_prime]
return prime_list
# 示例
input_number = int(input("请输入一个大于2的自然数: "))
prime_numbers = sieve_of_eratosthenes(input_number)
print(f"小于{input_number}的所有质数是: {prime_numbers}")
python写一个欧拉筛选法求质数
好的,我可以回答这个问题。欧拉筛法是一种用于求解一定范围内质数的算法,其主要思想是通过不断筛选数列中的数,得到最终的质数序列。以下是 Python 代码示例:
```
def euler_sieve(n):
primes = []
is_prime = [True] * (n+1)
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
for j in primes:
if i*j > n:
break
is_prime[i*j] = False
if i % j == 0:
break
return primes
```
通过调用 `euler_sieve(n)` 函数,可以得到不超过 n 的所有质数。
阅读全文