优化性能 - 写出质数

Question

问题是质数- 解决方案没有有效实施。

我听说过埃拉托色尼筛。

还有

---

哪些其他方法可以实现素数 - 以更有效的方式？

n = int(input())
suma = 0
m = 0
while m < n:
if n > 100000:
break
x = int(input())
if 1 < x < 10000:
for i in range(x):
if x % (i + 1) == 0:
suma += 1
if suma == 2 and x != 2:
m += 1
print('o')
suma = 0
else:
m += 1
print('x')
suma = 0

---

解决方案之一：https://medium.com/@dhruvpatel1057/generate-prime-numbers-in-python-using-segmented-sieve-of-eratosthenes-245b79da6687

Answer 1

你正在使用一种非常幼稚的方法来进行素数检查。

作为一个一般幼稚但不那么多的方法，我建议使用威尔逊定理作为素数检查器。使用math.factorial而不是 python 循环应该可以为您提供一些合理的速度提升，同时保持代码相当简单。

Answer 2

我听说过埃拉托色尼筛 - 但不知道如何实现它。

这不是埃拉托色尼本身的筛子，但人们在提到它时通常会谈论的是，当你找到一个素数时，你会遍历所有候选者并删除其因素("筛选"它们，因此得名(，新的第一个候选者是序列中的下一个素数。

不过，有比筛选所有东西更有效的素数测试，请查看"素数测试"维基百科页面以获取示例。

Answer 3

此代码将生成用户请求的质数数量。它非常有效，可以在毫秒内计算出前一千个素数。

amount = int(input("Enter the amount of prime numbers you would like to see: "))
primes = []
num = 1
while len(primes) < amount:
num += 1

# If num is bigger than 1, and is 2 or is odd, and when divided by all the number from 3 to num's square root plus 1 (excluding even numbers), there is always a remainder.
if num > 1 and (num == 2 or num % 2 != 0) and all(num % divisor != 0 for divisor in range(3, int(num ** 0.5) + 1, 2)):
primes.append(num)

print(f"The first {amount} prime numbers are:n{primes}")

Answer 4

这是示例代码，列出素数，并从此列表中检查要处理的数字是否被除，如果没有被除，那么它是素数，否则不是

# your code goes here
x = int(input())
prime =[]
for i in range(2,x):
if i not in prime:
if prime == []:
prime.append(i)
else:
check = 1
for j in prime:
if i%j==0:
check = 0 
break
if check:
prime.append(i)
print(prime)