Python程式設計之歐拉計劃47~48

• 歐拉計劃
• • 47、找出最小的具有四個不同質數因子的四個連續整數
  • 48、求前1000項的自幂方數的和的最後10位數字

歐拉計劃

歐拉計劃（Project Euler）。

47、找出最小的具有四個不同質數因子的四個連續整數

前兩個連續數字有兩個不同的質因數是：

14 = 2 × 7 , 15 = 3 × 5 14 = 2×7,\quad 15 = 3×5 14=2×7,15=3×5

前三個連續數字有三個不同的質因數：

644 = 2 2 × 7 × 23 , 645 = 3 × 5 × 43 , 646 = 2 × 17 × 19 644 = 2^2×7×23, \quad645 = 3×5×43, \quad646 = 2×17×19 644=22×7×23,645=3×5×43,646=2×17×19

找到前四個連續的整數，每個整數有四個不同的質因數。這些數字中的第一個是什麼？

# 如果n有四個不同質因數，傳回True
def is_factor4(n):
    fs = set()
    while n > 1:
        for i in range(2, n + 1):
            if n % i == 0:
                n = n // i
                fs.add(i)
                break
    return len(fs) == 4


fc = 0
for i in range(2 * 3 * 5 * 7, 1000000):
    if is_factor4(i):fc += 1
    else:fc = 0
    #連續4個
    if fc == 4:
        print(i - 3)
        break

           

輸出：

134043

48、求前1000項的自幂方數的和的最後10位數字

前10項的自幂方數的和為

    1 1 + 2 2 + 3 3 + … + 1 0 10 = 10405071317   1^1 + 2^2 + 3^3+ … + 10^{10}= 10405071317   11+22+33+…+1010=10405071317

求前1000項的自幂方數的和的最後10位數字。

輸出：

9110846700