python求解小于100的所有素数
时间: 2023-11-09 10:48:28 浏览: 33
用筛选法可以求解小于100的所有素数。该方法的思路是先假设所有的数都是素数,然后从2开始,将该数的所有倍数标记为合数。最后,剩下的未被标记的数就是素数。
在Python中,可以使用以下代码实现:
```python
def find_prime(n):
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False
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
primes = []
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
return primes
primes = find_prime(100)
print(primes)
```
以上代码将会输出小于100的所有素数:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]。
相关问题
python使用筛选法求解小于n的所有素数
Python使用筛选法求解小于n的所有素数的方法如下:
1. 首先创建一个长度为n的布尔数组,初始化为True,表示所有数都是素数。
2. 从2开始遍历数组,如果当前数是素数,则将它的倍数标记为非素数,即将对应位置的布尔值设为False。
3. 遍历完数组后,所有布尔值为True的位置所对应的数就是小于n的所有素数。
下面是Python代码实现:
def sieve_of_eratosthenes(n):
is_prime = [True] * n
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, i):
is_prime[j] = False
return [i for i in range(n) if is_prime[i]]
# 示例
print(sieve_of_eratosthenes(20)) # 输出 [2, 3, 5, 7, 11, 13, 17, 19]
编写python程序,使用筛选法求解小于n的所有素数
下面是一个使用筛选法求解小于n的所有素数的python程序:
```python
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的列表,用于记录每个数字是否为素数
is_prime = [True] * (n + 1)
# 0和1不是素数,将其标记为False
is_prime[0] = is_prime[1] = False
# 从2开始,遍历到n的平方根
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
# 如果i是素数,则将i的倍数标记为False
for j in range(i ** 2, n + 1, i):
is_prime[j] = False
# 返回小于n的所有素数
return [i for i in range(2, n + 1) if is_prime[i]]
# 测试程序
print(sieve_of_eratosthenes(30)) # 输出 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
```
在上面的程序中,我们使用了一个长度为n+1的列表is_prime来记录每个数字是否为素数。初始时,我们将所有数字都标记为素数(True),然后从2开始,遍历到n的平方根,如果当前数字i是素数,则将i的倍数标记为非素数(False),最后返回小于n的所有素数。