3

问题:迭代一个整数并在其中找到其他整数,然后如果该整数包含它们,则将其丢弃的最佳方法是什么?

长版:

我一直在努力提高我的 Python 技能,尝试为 Project Euler 的问题提供有效的解决方案。在经历了大约 20 个问题后,我发现虽然我可以解决这些问题,但我的解决方案通常是不优雅和笨拙的(即丑陋和缓慢)。问题的结构方式,我认为我需要学习一些更好的解决方案,因为更复杂的东西会加剧这些低效率。

无论如何,今天我正在处理问题 35,它要求所有小于 1,000,000 的圆素数。我已经制作了一个低于 1,000,000 的所有素数的列表,并且我构建了一个小框架来吐出下面这些素数的排列,我计划为每个排列测试素数:

def number_switcher(number):
  number = [num for num in str(number)]
  numlist = [''.join(num) for num in list(itertools.permutations(number))]
  return [int(num) for num in numlist]

正如您可以想象的那样,在所有素数上运行它然后测试每个可能的素数排列,这不是解决问题的方法。

然后我突然想到,在我开始运行排列之前,我可以丢弃所有包含偶数的数字(假设它们长于一位)或任何包含五的数字。

这是我真正迷路的地方。尽管看起来很简单,但经过两天的尝试,我还是想不通,如何扔掉其中包含偶数或 5 的多位数字。

这是我尝试过的(假设所有低于 1,000,000 的素数列表称为“素数”):

 [num for num in primes if any(x for x in '024685' in str(num))] # failed: 'bool' object is not iterable

然后我尝试了以下方法:

for prime in primes:
  if '0' in str(prime):
    primes.remove(prime)

>>>>len(primes)
4264

这将我的素数列表减少了一半。好的,所以也许我走在正确的轨道上,我只需要一个丑陋的“如果 str(prime) 中的 '0' 或 str(prime) 中的 '2'”等。

但奇怪的是:当我检查我的“素数”列表时,它仍然有带“0”的素数。在新的素数列表上再次运行相同的操作,我得到以下结果:

 for prime in primes:
   if '0' in str(prime):
     primes.remove(prime)
>>>>len(primes)
4026

...结果再次下降到:

>>>>len(primes)
3892
....
3861 # again
....
3843 #and again

也许我在这里遗漏了一些明显的东西,但似乎第一个 if-test 应该找到任何带有“0”的素数并删除它们?

最后,我还尝试了以下方法,这看起来很糟糕,因为它毫无意义地在 str-integer 火车轨道上来回跳跃,但它似乎只是必须工作:

for num in primes:
  for d in str(num):
    if (int(d) % 2 == 0 or int(d) == 5):
      primes.remove(num)   # doesn't work: ValueError: list.remove(x): x not in list 
    else:
      pass

我觉得我不应该在这个问题上扯出我的头发,但这让我有点疯狂,可能是因为我已经到了我只是想找出一个解决方案的地步,我的尝试越来越少清醒。

这是我的问题:

迭代一个整数并在其中找到其他整数,然后将那个愚蠢的整数扔掉(如果它包含它们)的最佳方法是什么?

感谢您的帮助/阅读。

脚注:这是我在这里提出的第一个问题,但几个月来我已经从这个网站的指导中受益。如果这个问题/解决方案存在,我深表歉意,但我寻找它并找不到一种方法来拼凑解决方案。大多数搜索结果显示为“如何判断整数是否为偶数”。

4

2 回答 2

2

@root 是正确的,您关于如何优化它的假设是错误的,但我认为指出为什么您正在做的事情在 Python 级别上不起作用会很有用。

你的布尔问题

[num for num in primes if any(x for x in '024685' in str(num))] # failed: 'bool' object is not iterable

'024685' in str(num)首先被评估,所以它等同于for x in True- 这是不可能的。上面会写成:

[num for num in primes if not any(ch in '024685' for ch in str(num)]

它从每个字符中获取str(num)并检查它是否是'024685'.

你的清单问题

这里有一条经验法则——不要修改你正在迭代的东西。如果你用 a 来尝试这个,dict你会抛出一个异常 - 但对于 alist它可能会默默地出错,但偶尔会中断。

从列表中删除多个值时,最好构建一个仅保留所需值的新列表,例如:

no_zero = [num for num in primes if '0' not in str(num)]

如果您想修改原始素数:

primes[:] = no_zero

您的最后一个示例也因 而失败.remove(),将上述内容放在一起可以写成:

[num for num in primes if not any(num % i == 0 for i in (2, 5)]

杂项

您可能希望考虑将素数存储在set- 因为您不关心素数的顺序,并且对于成员资格测试会更快。

于 2012-11-08T07:32:17.247 回答
0

谢谢,乔恩克莱门茨。我今天能够使用以下脚本解决问题(请注意,我必须确保“024685”剥离器没有剥离“2”和“5”,因为它们是答案的一部分,这让我有一段时间没有...):

import math
import itertools

def prime_test(number):
  if all(number % x != 0 for x in range(2, int(math.sqrt(number)) + 1)):
    return True
  else:
return False

def find_primes(limit):
  primes = [2]
  for x in range(3, limit + 1, 2):
    if prime_test(x):
      primes.append(x)
    else:
      pass
  return primes

def circulate(number):
  circ_list = [number]
  x = 1
  while x < len(str(number)):
    number = str(number)[1:] + str(number)[0]
    circ_list.append(number)
    x += 1
  return circ_list

def main():
  primes = find_primes(1000000)
  no_evens = [x for x in primes if not any(ch in '024685' for ch in str(x) if len(str(x)) > 1)]

  circular_primes = [] 
  for prime in no_evens:
    if all(prime_test(x) for x in circulate(prime)):
      circular_primes.append(prime)
    else:
      pass

  return circular_primes, len(circular_primes)

if __name__ == '__main__':
  print(main())

我没有意识到的另一件事是我只是应该旋转数字,而不是提供它的所有可能排列。当人们试图解决问题时,这些陷阱可能会让他们失望。

于 2012-11-11T01:34:09.597 回答