输入一个正整数n,求n以内的素数。输入一个正整数n,求n以内的素数。请使用数组用筛选法实现。
时间: 2024-11-25 18:11:05 浏览: 54
筛选法(Sieve of Eratosthenes)是一种古老的算法,用于查找一定范围内的所有质数。下面是使用数组实现这个算法的基本步骤:
1. 初始化一个大小为n+1的布尔数组isPrime[],并将所有元素设为true。这表示从0到n的所有数字都是潜在的质数。
2. 从2开始遍历,因为2是最小的质数。如果isPrime[2]为true,则将2及其后续所有的偶数(4、6、8...)标记为非质数,因为它们能被2整除。这里可以跳过偶数,提高效率。
3. 对于每个找到的质数i,检查i的平方小于等于n的情况。对于所有i的倍数(除了i本身),将其对应的isPrime值设为false。例如,如果找到了5,就将5的倍数(如10、15、20...)标记为非质数。
4. 遍历结束后,isPrime[]数组中仍然为true的位置所对应的数值就是该范围内内的素数。
```python
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5) + 1): # 只需检查到√n
if is_prime[i]:
for j in range(i*i, n + 1, i): # 跳过已知的合数倍数
is_prime[j] = False
primes = [i for i, prime in enumerate(is_prime) if prime]
return primes
n = int(input("请输入一个正整数: "))
primes = sieve_of_eratosthenes(n)
print(f"在 {n} 以内的素数有: ", primes)
阅读全文
相关推荐


















