Google 拼图欧拉数

Question

这个post是双重的。我是 Python 的新手。

第一部分。

这是旧 Google 谜题的代码： 'First 10 digit prime number in the consecutive digits of e' (https://google-tale.blogspot.ca/2008/07/google-billboard-puzzle.html)

euler = '7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190115738341879307021540891499348841675092447614606680822648001684774118537423454424371075390777449920695517027618386062613313845830007520449338265602976067371132007093287091274437470472306969772093101416928368190255151086574637721112523897844250569536967707854499699679468644549059879316368892300987931277361782154249992295763514822082698951936680331825288693984964651058209392398294887933203625094431173012381970684161403970198376793206832823764648042953118023287825098194558153017567173613320698112509961818815930416903515988885193458072738667385894228792284998920868058257492796104841984443634632449684875602336248270419786232090021609902353043699418491463140934317381436405462531520961836908887070167683964243781405927145635490613031072085103837505101157477041718986106873969655212671546889570350354'


for i in range(len(euler) - 3):
    if (euler[i + 3]== '1' or euler[i + 3]== '3' or euler[i + 3]== '7' or euler[i + 3]== '9'):
        number = int(euler[i:i + 3])
        for a in range(2, round(number**0.5)):
           if number % a == 0:
             break
        else:
           print(number),
           break

奇怪的是，使用上面的代码我可以找到正确的答案，即 7427466391（编译需要 4500 万）但是当我测试 3 位代码时，它给了我 709，这是不正确的，因为前 3 位是质数数字是 281 range(3,6).

我该如何解决这个问题？

第二部分。

这是一种被认为是最快找到素数的算法 (https://en.wikipedia.org/wiki/Primality_test)（请参阅页面中间的伪代码）。这是我的代码，但它不起作用，我进入了一个无限循环。

for i in range(len(euler) - 3):
    if (euler[i + 3]== '1' or euler[i + 3]== '3' or euler[i + 3]== '7' or euler[i + 3]== '9'):
        number = int(euler[i:i + 3])
        for y in range(2, number-1):
            while y * y <= number:
                if (number % y != 0 or  number % (y+1) != 0):
                break

我该如何解决？

Answer 1

对于你的第一部分，你正在掌握 Python 范围和切片的右端非包含属性。但是，当您只是通过索引查找某个元素时，您是否还应该关心它？我的意思是，对于从位置 i 开始的数字，第三个数字是否真的在 i+3 索引？

对于你的第二部分，我不太清楚你的代码和伪代码之间的映射。

一般提示。您可以将 prime_check 逻辑划分为 returns True 或 False 的函数，并在每次获得数字时调用该函数，然后决定是否要打印它并中断或继续。此外，您对 1、3、7、9 进行的比较并缩写为 in。

Answer 2

对于第一部分，将 '3' 替换为 '2' 以便它检查第 3 个数字的奇数，而不是第 4 个：

euler[i + 3]== '1' or euler[i + 3]== '3' or euler[i + 3]== '7' or euler[i + 3]== '9'):

更改为

euler[i + 2]== '1' or euler[i + 2]== '3' or euler[i + 2]== '7' or euler[i + 2]== '9'):

同样地，想想 for 循环中的范围应该延伸到什么（即 len - 2 或 len -3），即使它不适用于这个例子。

一般来说，完全避免使用 magic numbers。定义变量或接受输入以设置 N = 3 或 10...

此外，添加 if 条件不会给您带来太多好处，只会带来错误的可能性（如上所述）。 过早的优化是万恶之源

对于第二部分，当你 break 你的内循环时，你并没有真正建立任何素数。你可以做一些简单的事情，比如设置一个标志。在这里，我修改了您的程序以提供一个示例：

euler = '7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190115738341879307021540891499348841675092447614606680822648001684774118537423454424371075390777449920695517027618386062613313845830007520449338265602976067371132007093287091274437470472306969772093101416928368190255151086574637721112523897844250569536967707854499699679468644549059879316368892300987931277361782154249992295763514822082698951936680331825288693984964651058209392398294887933203625094431173012381970684161403970198376793206832823764648042953118023287825098194558153017567173613320698112509961818815930416903515988885193458072738667385894228792284998920868058257492796104841984443634632449684875602336248270419786232090021609902353043699418491463140934317381436405462531520961836908887070167683964243781405927145635490613031072085103837505101157477041718986106873969655212671546889570350354'

for i in range(len(euler) - 2):
    if (euler[i + 2]== '1' or euler[i + 2]== '3' or euler[i + 2]== '7' or euler[i + 2]== '9'):
        number = int(euler[i:i + 3])
        for y in range(2, number-1):
            isPrime = True
            while y * y <= number:
                if (number % y != 0 or  number % (y+1) != 0):
                  isPrime = False # The number is not prime
                  break  # Exit loop

            if isPrime:  # Nothing was able to factorize the number
              print(number) # Print and leave
              exit(0)

但是，您的代码确实很糟糕，需要对不同的边缘情况进行大量关注和测试。

Google 拼图欧拉数

Google Puzzle Euler Number

python

eulers-number

第一部分。

第二部分。