Euler 3 Python。把质数放入列表

我仍然很新的python，我试图从600851475143所有的素数到列表中。但是，我不断收到列表中的随机数字，而不是素数。我不确定我会出错的地方。感谢您的时间Euler 3 Python。把质数放入列表

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

来源

2015-05-04 TheNuker

没有与此算法的主要问题。建议：在循环中添加几条打印语句，以查看算法产生的数字。不要试图处理这个庞大的号码，除非你确定你的代码可以在你可以手动检查的小号码上正常工作。在相关说明中，您可能会发现使用铅笔和纸张遵循您的算法很有帮助。 –

目前你追加到每一次if (num % i) == 0prime_factor。因此，例如，如果num=12（不是素数）和i=5，那么您将会追加到prime_factor。

取而代之的是，如果它有没有除数，那么只应该追加，而不是只有一个数字不能均匀分配。

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

来源

2015-05-04 14:46:22 tom10

什么是最好的方式来处理大数字？到目前为止，我已经在我的 – TheNuker

类只有了解range和xrange一般情况下，我认为这是对的欧拉问题的目标，以帮助解决。我在这里帮了忙，因为这是一个与问题核心无关的编程问题。至少在你寻求下一步的帮助之前，你自己尝试一下。欧拉问题意味着很难。 – tom10

600851475143不_that_巨大的：它的最大素因子必须小于一百万，实际上是7000下真，这将会是在有限的32位整数的语言问题，但它是因式分解在微风Python甚至用一个相当简单的算法。 –

对于大数量，这将运行得相当缓慢。考虑算法尝试寻找num = 1000000的主要因素的情况。嵌套的FOR循环将在下一个数字被考虑之前生成100万次操作！

考虑使用Eratosthones筛来获得所有素数达到某个整数。它不如某些其他Sieve效率高，但易于实施。花一些时间在实施之前阅读筛选背后的理论 - 这将有助于您理解以后的问题。

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

来源

2015-05-04 14:55:47 manglano

我同意TheNuker需要在他们的算法上工作，但在这里试用部门已经足够 - 他们并不需要使用筛子。 –

下面是融通ň更好的算法。我会用文字来描述它，所以你可以自己编写代码。

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并返回到步骤2.现在步骤2中的测试未得到满足，步骤3中的剩余部分为1 ，因此在步骤4中设置f = 4并返回步骤2.现在步骤2中的测试未得到满足，步骤3中的剩余部分为3，因此在步骤4中设置了f = 5并返回步骤2

现在步骤2中的测试未得到满足，但步骤3中的剩余部分为0，因此5是13195的因子;输出5，设置为n = 2639，并返回步骤2.现在步骤2中的测试未得到满足，步骤3中的剩余部分为4，因此在步骤4中设置了f = 6并返回步骤2。现在，在步骤2中的试验是不满足，则在步骤3中余数为5，因此在步骤4中设置˚F = 7，并返回到步骤2。

现在在步骤2中的试验是不满足，但步骤3中的余数为0，所以7是2639的因子（也是13195）;输出7，设置为n = 377，并返回步骤2.现在步骤2中的测试未得到满足，步骤3中的剩余部分为6，因此在步骤4中设置了f = 8并返回步骤2。以这种方式继续，直到f = 13。

现在，在步骤2中的试验是不满足，但是在步骤3中余数为0，所以图13是377（以及2639和13195）的一个因素;输出端13，设置Ñ = 29，并返回到步骤2中步骤2在这里，测试是满足，因为13×13 = 169，其大于29，所以29是质数，它输出和停止。最终分解为5 * 7 * 13 * 29 = 13195.

的600851475143件作品中完全相同的方式的分解，不同之处在于它需要更长的时间。有更好的方法来整数。但是这个算法很简单，对于PE3来说已经足够了。

来源

2015-05-04 20:17:28 user448810

Euler 3 Python。把质数放入列表

回答

相关问题