6.连续数字最大乘积
在下面这个1000位正整数中，连续4个数字的最大乘积是9 × 9 × 8 × 9 = 5832。
7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843
8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557
6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749
3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776
6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397
5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474
8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586
1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408
0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606
0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
解题思路：
通过滑动窗口实现，即控制窗口的大小为13，如果窗口所对的字符串中包含0，则直接将窗口的起点跳到0的下一位，否则计算乘积并与之前的最大值比较并更新，同时窗口后移一位，并循环。
通过简单循环实现，每次计算13位的乘积，同时更新最大值、再后移一位，如果某一位为0时不计算、后移一位再计算。
代码如下：
def str_product(num_str): res = 1 for num in num_str: res *= int(num) return res def successive_13_product1(): '''滑动窗口''' num_str = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843'\ '8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557'\ '6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749'\ '3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776'\ '6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397'\ '5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474'\ '8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586'\ '1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408'\ '0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606'\ '0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450' start = 0 end = 12 max_result = 1 sub_str = num_str[start:end + 1] if '0' not in sub_str: res = str_product(sub_str) if res > max_result: max_result = res while end < 999: end += 1 if num_str[end] == '0': start = end + 1 end = start + 12 else: start += 1 sub_str = num_str[start:end + 1] res = str_product(sub_str) if res > max_result: max_result = res return max_result print(successive_13_product1()) def successive_13_product2(size): '''循环''' num_str = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843'\ '8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557'\ '6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749'\ '3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776'\ '6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397'\ '5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474'\ '8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586'\ '1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408'\ '0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606'\ '0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450' max_result = 1 str_len = len(num_str) for i in range(str_len - size): res = 1 for j in range(i, i + size): if num_str[j] == '0': break res *= int(num_str[j]) if res > max_result: max_result = res return max_result print(successive_13_product2(13))
输出：
23514624000 23514624000
性能分析：
从前面的分析可以看出，第一种方式循环的次数更少、运行时间更短。
7.特殊毕达哥拉斯三元组
毕达哥拉斯三元组是三个自然数a < b < c组成的集合，并满足a2 + b2 = c2，
例如，32 + 42 = 9 + 16 = 25 = 52。
有且只有一个毕达哥拉斯三元组满足 a + b + c = 1000。求这个三元组的乘积abc。
解题思路：
可以看到，这样的三元组可以构成直角三角形，a是短直角边、b是长直角边、c是斜边，最简单的实现方式是两层嵌套循环，循环的范围都是1-1000，但是显然这样循环次数会比较大。
经过分析可以知道，a是最短边，所以其长度是小于周长的三分之一的，所以循环范围为1-1000/3，b是大于a的，且b+c=1000-a、b<c，所以b的范围是a+1-(1000-a)/2，c即为1000-a-c，显然，此时循环次数会大大减小。
代码如下：
def get_pythagorean_triple(): res = 1 for i in range(1, 1000 // 3 + 1): for j in range(i + 1, (1000 - i) // 2 + 1): k = 1000 - i - j if i ** 2 + j ** 2 == k ** 2: res *= (i * j * k) break return res print(get_pythagorean_triple())
输出：
31875000
性能分析：
本方法相比于简单循环，大大降低了循环次数，相率有所提升。
8.素数的和
所有小于10的素数的和是2 + 3 + 5 + 7 = 17。
求所有小于两百万的素数的和。
解题思路：
实现函数判断每一个数是否为素数，并相加即可。在判断素数时可以进一步减少循环次数，如果是大于2的偶数则肯定不是素数，则不需要进行循环，为奇数时，不需要再循环偶数。
代码如下：
def is_prime(n): is_prime = True if n < 2: is_prime = False elif n == 2: pass else: if n & 1 == 0: is_prime = False else: for i in range(3, int(pow(n, 0.5)) + 1, 2): if n % i == 0: is_prime = False break return is_prime def sum_prime(n): prime_sum = 0 for i in range(2, n + 1): if is_prime(i): prime_sum += i return prime_sum print(sum_prime(2000000))
输出：
142913828922
