(使用集合实现筛选法求素数)输入一个大于2的自\n然数,输出小于该数字的所有素数组成的集合。提示:\n一个数푛如果能被푥整除而得到푦,那么푚푖푛(푥,푦)≤\n√푛
时间: 2023-05-02 11:03:02 浏览: 108
python使用筛选法计算小于给定数字的所有素数
题意:使用集合实现筛选法求素数,输入一个大于2的整数,输出小于该数字的所有素数组成的集合。
解题思路:首先,由于题目要求使用集合实现,我们需要先创建一个空集合来存放所有素数。然后,我们从2开始,循环到输入的数字n。对于每个数i,我们需要判断它是否为素数。如果是素数,则将它加入我们创建的集合中。
那么如何判断一个数是否为素数呢?我们可以使用筛选法,从2开始将该数的倍数标记为合数,然后继续往下遍历。如果一个数是合数,则说明它之前已经被标记过了,可以直接跳过。
最后,我们将所有素数组成的集合返回即可。以下是代码实现:
```python
def find_prime(n):
primes = set() # 创建一个空集合来存放素数
is_prime = [True] * n # 创建一个n个元素的布尔数组,用于标记素数和合数
is_prime[0] = is_prime[1] = False # 0和1都不是素数
for i in range(2, n):
if is_prime[i]: # 如果i是素数,则将它加入集合中
primes.add(i)
for j in range(i*i, n, i): # 将i的倍数标记为合数
is_prime[j] = False
return primes
```
以上代码中,我们将素数的判断和集合的添加合并在了一起,简化了代码的实现。测试一下:
```python
>>> find_prime(10)
{2, 3, 5, 7}
>>> find_prime(20)
{2, 3, 5, 7, 11, 13, 17, 19}
>>> find_prime(30)
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
```
最后,题目中还提醒我们需要注意一下输入的整数不能被调整,那么我们只需要在循环中将范围设为[2, n+1)即可避免出现等于n的数。同时,也需要注意集合添加元素时的语法,应该使用add()方法而不是append()。
阅读全文