温馨提示×

python怎么求整数n以内的素数

小亿
224
2023-08-22 21:10:28
栏目: 编程语言

可以使用以下方法来求整数n以内的素数:

  1. 创建一个空的列表primes来存储素数。

  2. 创建一个长度为n+1的布尔类型列表is_prime,初始化所有元素为True。其中is_prime[i]表示数字i是否为素数。

  3. 从2开始,遍历2到n的所有数字i:

  • 如果is_prime[i]True,则将i添加到primes列表中,并将is_prime中i的所有倍数(除了i本身)设置为False
  1. 返回primes列表。

以下是一个使用上述方法求解整数n以内的素数的示例代码:

def find_primes(n):
primes = []
is_prime = [True] * (n+1)
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
for j in range(i*2, n+1, i):
is_prime[j] = False
return primes
n = int(input("请输入一个整数n:"))
result = find_primes(n)
print(f"整数{n}以内的素数为:{result}")

这个代码会提示用户输入一个整数n,然后调用find_primes函数来求解n以内的素数,并将结果打印出来。

1