[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()

PS:我知道我应该从799999999开始,因为:

GergS:每9位数和8位数的pandigital数可被3整除.

Answer 1

你的IsPrime功能非常慢.它可以快速计算,987654321是可分3和987654320可划分由二,然而,987654319是素数,它需要非常非常长,检查其对所有除数如此看来,如果它停止.

这个问题需要的不仅仅是简单的计算,就像你所做的那样.计算素数是一个缓慢的过程,因此您应该对其进行优化,例如:

• IsPandigital之前测试IsPrime,
• 更好的是,创建一个只有pandigital数字的列表,并进行主要测试.提示:pandigital数字是:[987654321,987654312,987654231,987654213,...]
• 你不必制作循环while i < No- 它足以达到目标 sqrt(No).
• 以数字0,2,4,5,6或8结尾的数字永远不是素数
• 另一种选择可能是计算所有的n位素数,然后选择最大的pandigital数.

你的其他问题:

• 您正在计算最大的9位数 pandigital prime.这个问题说:"最大的N位 pandigital素",所以你应该能够计算根据参数任意长度
• 你不应该像你写的那样从799999999开始.你应该简单地跳过n = 3,n = 5,n = 6,n = 8和n = 9的计算,因为这些都不是素数.