python - 优化性能 - 写出质数

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

标签： python

Answer 1

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

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