用Python编写函数,找出1~num之间的所有质数。
时间: 2023-08-31 18:33:34 浏览: 277
### 回答1:
可以使用埃氏筛法来实现这个功能,该算法的时间复杂度为O(nloglogn)。
以下是代码实现:
```python
def find_primes(num):
is_prime = [True] * (num + 1)
primes = []
for i in range(2, num + 1):
if is_prime[i]:
primes.append(i)
for j in range(i*2, num + 1, i):
is_prime[j] = False
return primes
```
该函数会返回一个列表,包含所有小于等于num的质数。
### 回答2:
要编写一个Python函数来找出1~num之间的所有质数,可以使用以下代码:
```python
def find_prime(num):
primes = [] # 用于存储质数的列表
for i in range(2, num + 1): # 循环从2到num
is_prime = True # 假设i是质数
for j in range(2, int(i ** 0.5) + 1): # 循环从2到i的平方根
if i % j == 0: # 如果i能被j整除,则i不是质数
is_prime = False
break
if is_prime: # 如果is_prime为True,则i是质数
primes.append(i) # 将i添加到质数列表中
return primes
num = int(input("请输入一个整数num:"))
result = find_prime(num)
print(f"1~{num}之间的所有质数为:{result}")
```
这个函数的原理是,对于1~num的每个数,使用两个嵌套循环判断该数是否为质数。外层循环从2到num,内层循环从2到当前数的平方根,如果当前数能被任何一个数整除,则它不是质数,is_prime变量将被设为False。如果is_prime仍然是True,则当前数是质数,将其添加到primes列表中。最后返回质数列表。
例如,如果输入num为10,则函数将返回[2, 3, 5, 7],因为1~10之间的质数为2、3、5和7。
### 回答3:
编写一个函数 `find_prime(num)`,实现找出1~num之间的所有质数的功能。
```python
def find_prime(num):
prime_numbers = [] # 存储质数的列表
for n in range(2, num + 1): # 从2开始到num遍历每个数
is_prime = True # 默认为质数
# 判断是否能被小于当前数的质数整除
for prime in prime_numbers:
if n % prime == 0:
is_prime = False # n被整除,则n不是质数
break
if is_prime:
prime_numbers.append(n) # 将n添加到质数列表中
return prime_numbers
num = int(input("请输入一个正整数:"))
prime_nums = find_prime(num)
print(f"{num}之前的所有质数为:{prime_nums}")
```
使用 `find_prime` 函数,在1~num之间找出所有质数,并将结果存储在 `prime_nums` 列表中。最后输出结果。
示例输出:
```
请输入一个正整数:30
30之前的所有质数为:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
```
该函数通过判断一个数是否能被之前的质数整除,来确定该数是否为质数。在循环中,遇到能整除的数即停止判断,可有效减少判断的次数,提高运行效率。
阅读全文