欧拉 3 Python。将质数放入列表中

Question

我对 python 还是很陌生，我正在尝试将 600851475143 中的所有质数放入一个列表中。但是，我一直在列表中随机获取数字而不是素数。我不确定我哪里出错了。谢谢你的时间

import math
factors_list = []
prime_factors = []

def number_factors(s):
    s = int(math.sqrt(s))
    for num in range(2, s):
        for i in range(2, num):
            if (num % i) == 0:
                factors_list.append(num)
            else:
                prime_factors.append(num)

number_factors(600851475143)

print factors_list
print prime_factors

Answer 1

目前您每次 if (num % i) == 0 都追加到 prime_factor。因此，例如，如果 num=12（不是质数）和 i=5，您将对 prime_factor.

进行追加

相反，如果它根本没有没有个除数，您应该只追加，而不仅仅是一个数字不均匀。

虽然我会提前警告你，这个问题不仅仅是关于计算素数，而是 600851475143 是一个非常大的数字。因此，您可能应该将当前的代码作为学习练习来使用，但您需要重新考虑完整解决方案的方法。

Answer 2

对于大数字，这将运行相当慢。考虑算法试图找到 num = 1000000 的质因数的情况。在考虑下一个数字之前，您的嵌套 FOR 循环将生成 100 万次操作！

考虑使用 Eratosthones 筛法将所有素数计算到某个整数。它不如某些其他筛子有效，但易于实施。在实施之前花一些时间阅读筛子背后的理论——这将有助于您理解后面的问题。

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 3

这里有一个更好的因式分解算法 n。我会用文字描述它，这样你就可以自己编写代码了。

1) Set f = 2. Variable f represents the current trial factor.
2) If f * f > n, then n must be prime, so output n and stop.
3) Divide n by f. If the remainder is 0, then f is a factor of n,
     so output f and set n = n / f, then return to Step 2.
4) Since the remainder in the prior step was not 0, set f = f + 1
     and return to Step 2.

比如因子13195，先设f = 2；第2步的测试不满足，第3步的余数为1，所以在第4步中设置f = 3和return到第2步。现在步骤中的测试2不满足，第3步的余数为1，所以第4步设置f = 4和return到第2步。现在第2步的测试不满足，第三步的余数是3，所以在第四步设置f = 5和return到第二步

现在第2步的测试不满足，但是第3步的余数为0，所以5是13195的因数；输出5，设置n = 2639，并且return到第2步。现在第2步的测试不满足，第3步的余数是4，所以第4步set f = 6 and return to Step 2. 现在Step 2的test不满足，step 3的余数是5，所以在Step 4 set f = 7 和 return 到第 2 步。

现在第2步的测试不满足，但是第3步的余数为0，所以7是2639（也是13195）的因数；输出7，设置n = 377，并且return到第2步。现在第2步的测试不满足，第3步的余数是6，所以第4步将f = 8和return设置为步骤2。以这种方式继续直到f = 13。

现在第2步的测试不满足，但是第3步的余数为0，所以13是377的因数（也是2639和13195的因数）；输出13，设置n = 29，return到第2步。这里第2步的测试是满足的，因为13 * 13 = 169 大于 29，所以 29 是质数，输出它并停止。最后的因式分解是 5 * 7 * 13 * 29 = 13195.

600851475143 的因式分解以完全相同的方式进行，只是需要更长的时间。有更好的方法来分解整数。但是这个算法很简单，PE3也够用了。

欧拉 3 Python。将质数放入列表中

Euler 3 Python. Putting the prime numbers into a list

python

math

primes

prime-factoring