[Python/Project Euler]问题 41

Question

我正在尝试解决第41个问题，但是我不知道为什么我的代码在987654319这个数字处停止了：

def IsPandigital(No):
 a = sorted(str(No))
 for i in range(1,10):
  if a[i - 1] != str(i):
   return False
 return True
def IsPrime(No):
 i = 2
 while i < No:
  if No % i == 0:
   return False
  i += 1
 return True
i = 987654321
while i > 0:
 print i
 raw_input()
 if IsPrime(i) == True and IsPandigital(i) == True:
  print i
  break
 i -= 1
print i
print "EOP"
raw_input()

附注：我知道我应该从799999999开始，因为：

GergS: 每个9位和8位的全数字（即包含1到9所有数字的）数字都是可以被3整除的。

Answer 1

试着用它的一个功能叫做 itertools.permutations 来生成所有的全数字组合，然后检查这些组合是否是质数。这个功能会生成你给它的字符串的所有排列组合。

比如说：

itertools.permutations('9876543210')

你可以像上面说的那样缩小你的搜索范围，'9876543210' 只是一个例子。

Answer 2

找质数的这个过程比找全数字的过程要慢很多，所以我们需要把它们的执行顺序调换一下。应该是这样：

if IsPandigital(i) == True and IsPrime(i) == True:

Answer 3

你的 IsPrime 函数运行得很慢。它很快就算出987654321可以被3整除，987654320可以被2整除。然而，987654319是一个质数，检查它是否能被所有的数整除需要很长时间，所以看起来就像是程序卡住了一样。

这个问题需要的不仅仅是简单的计算。计算质数是一个比较慢的过程，所以你应该优化一下，比如：

• 在检查 IsPrime 之前先测试 IsPandigital，
• 更好的方法是先创建一个只包含全数字的列表，然后再进行质数测试。提示：全数字的数有： [987654321,987654312,987654231,987654213,...]
• 你不需要用 while i < No 的方式循环，只需要检查到 sqrt(No) 就可以了。
• 以0、2、4、5、6或8结尾的数字永远不是质数。
• 另一个选择是先计算出所有n位的质数，然后再找出最大的全数字数。

你还有其他问题：

• 你现在计算的是最大的9位全数字质数。题目说的是“最大的n位全数字质数”，所以你应该能根据参数计算任意位数的质数。
• 你不应该从799999999开始计算，正如你所写的。你应该直接跳过n=3、n=5、n=6、n=8和n=9的计算，因为这些都不是质数。