10001st prime, Project Euler Problem 7

https://projecteuler.net/problem=7

10001番目の素数を求める。まずは愚直に求めてみよう。

Solution 1

from datetime import datetime

def is_prime(num):
    for d in range(2, num):
        if num % d == 0:
            return False
    return True

# test is_prime()
print(is_prime(2)) # True
print(is_prime(3)) # True
print(is_prime(4)) # False
print(is_prime(17)) # True

def find_prime(nth):
    count = 0
    num = 1
    while count < nth:
        num += 1
        if is_prime(num):
            count += 1
    return num

# test find_prime()
print(find_prime(6)) # 13

start_time = datetime.now()
print(find_prime(10001)) # ?
exec_time = datetime.now() - start_time
print(exec_time)

答えは求められた。ただし処理時間が、

0:00:45.135762

45秒は時間かかりすぎだ。改善をしよう。

Solution 2

素因数かどうかはその数より小さい素因数でのみ割り切れるかをチェックすればよい。それまでに求めた素因数はprimesリストに保持するようにした。is_prine()関数が引数1つで一意な結果が返るものじゃなくなったのでfind_prime()関数内に統合している。

from datetime import datetime

def find_prime(nth):
    num = 1
    primes = []
    while len(primes) < nth:
        num += 1
        is_prime = True
        for p in primes:
            if num % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return num

# test find_prime()
print(find_prime(1)) # 2
print(find_prime(6)) # 13

start_time = datetime.now()
print(find_prime(10001)) # ?
exec_time = datetime.now() - start_time
print(exec_time)

これで処理時間は、

0:00:04.344577

約1/10の時間で求められるようになった。

Sum square difference, Project Euler Problem 6

https://projecteuler.net/problem=6

「2乗の数列の和」と「数列の和の2乗」をそれぞれ求めて、それらの差を求める問題。2乗の数列の和の一般解を求めて関数化してもいいが、項数100なので強引に計算してしまう。

Solution

def sum_of_squares(n):
    sum = 0
    for i in range(1, n + 1):
        sum += i ** 2
    return sum

def square_of_sum(n):
    sum = 0
    for i in range(1, n + 1):
        sum += i
    return sum ** 2

def difference(n):
    return square_of_sum(n) - sum_of_squares(n)

print(sum_of_squares(10)) # 385
print(square_of_sum(10)) # 3025
print(difference(10)) # 2640

print(difference(100)) # ?

Smallest multiple, Project Euler Problem 5

https://projecteuler.net/problem=5

1から20全ての数で割り切れる最小の数を求める問題。「割り切れる」という性質と素因数分解を考えると解決の糸口が見つけられた。例えば20で割り切れるとは、

20 × a = 22 × 51 × a

つまり素因数として2が2つ以上、5が1つ以上含まれている数。同様に16で割り切れる数は、

16 × b = 24 × b

20でも16でも割り切れる最小の数は2が4つ、5が1つのみ素因数として含まれていればよいので、

24 × 51 = 80

1から20までをそれぞれ素因数分解して素因数とその個数をチェック、それらの割り切れる条件を全て満たす最小の素因数組み合わせパターンを見つけて、そのパターンの素因数を全て掛け合わせれば期待する数値が求められそう(日本語ムズイ)

Solution

# https://projecteuler.net/problem=5

def prime_factorize(num):
    pfs = {}
    for div in range(2, num + 1):
        while num % div == 0:
            if div not in pfs:
                pfs[div] = 0
            pfs[div] = pfs[div] + 1
            num = num // div
    return pfs

pfs = {}
for num in range(2, 21):
    num_pfs = prime_factorize(num)
    for pf, c in num_pfs.items():
        if pf not in pfs:
            pfs[pf] = c
        else:
            pfs[pf] = max(pfs[pf], c)

result = 1
for pf, c in pfs.items():
    result = result * (pf ** c)

print(result)

今日の学び(Python)

  • Dictionary { key1: val1, key2 : val2 }
  • エントリーの有無は in 演算子使える
  • 全エントリーのループは for k, v in dic.items(): でOK
  • エントリー削除は del dic[key]

Largest palindrome product, Project Euler Problem 4

https://projecteuler.net/problem=4

palindrome、回文、つまり最上位の桁からの数字の並びと最下位の桁からの数字の並びとが同じ数値。2つの2桁の数値の積から求められる最大の回文数は、

9009 = 91 × 99

ということで、2つの3桁の数値の積から求められる最大の回文数を求めよっていう問題。

100〜999までの2値を動かして全パターンチェックすれば良さそうだけど、その場合は 900 × 900 = 810,000 回の演算か。とりあえず書いてみる。

Solution 1

# https://projecteuler.net/problem=4

from datetime import datetime

def is_palindrome(num: int) -> bool:
    num_str = str(num)
    num_len = len(num_str)
    idx = 0
    while idx < num_len:
        if num_str[idx] != num_str[-1 - idx]:
            return False
        idx += 1
    return True

# test
print(is_palindrome(123))
print(is_palindrome(12321))

# main
start_time = datetime.now()
result = 0
count = 0
for i in range(100, 1000):
    for j in range(100, 1000):
        count += 1
        if is_palindrome(i * j):
            result = max(result, i * j)
exec_time = datetime.now() - start_time

print(f"result: {result!r}")
print(f"count : {count!r}")
print(f"e_time: {exec_time!s}")

出力

False
True
result: (答えなので伏せておく)
count : 810000
e_time: 0:00:01.009521

重複した計算を省く

Solution 1 の場合、例えば 100 × 900 と 900 × 100 は同じなのでどちらか片方だけ計算すれば良いのでループが改善できそう。ネストした j 側のループのスタートを i からにする。

Solution 2

main処理だけ

# main
start_time = datetime.now()
result = 0
count = 0
for i in range(100, 1000):
    for j in range(i, 1000):
        count += 1
        if is_palindrome(i * j):
            result = max(result, i * j)
exec_time = datetime.now() - start_time

出力(計算回数と処理時間のみ)

count : 405450
e_time: 0:00:00.577004

半分ぐらいになった。

途中でループを打ち切る

最大値を求める問題なので「今求められている候補値よりも大きな値は出てこない」が判定できればループを打ち切れる。そのためには、

  1. 大きな数値からループを始める
  2. 例えば候補値が 900 × 800 の場合、800以下の2値は計算する必要ない

Solution 3

# main
start_time = datetime.now()
result = 0
count = 0
loop_limit = 100
for i in range(1000, 100, -1):
    for j in range(i, loop_limit, -1):
        count += 1
        if is_palindrome(i * j):
            result = max(result, i * j)
            loop_limit = j
            break
    if i < loop_limit:
        break
exec_time = datetime.now() - start_time

出力

count : 8055
e_time: 0:00:00.024518

いい感じで計算量が約 1 / 100 になった。やったぜ。

今日の学び(Python)

  • datetimeで処理時間計測
  • format string literal で文字列整形
  • {} で置換、!s で str() と等価、!r で repr() と等価
  • repr() は a printable representation of an object ってことで

Largest prime factor, Project Euler Problem 3

https://projecteuler.net/problem=3

与えられた数字の最も大きい素因数を求める問題。素因数を小さい順に出していって、その数字で割り切れるかをチェックすればいい?と最初考えたが計算効率が悪そう。しばらく考える。

そういえば最近数学ガールで読んだ「全ての自然数素数の積の形で一意に表現できる」っていうのを思い出す。

n = 2a * 3b * 5c * ...

つまり小さい素因数を順番に除算で取り除いていけば最後に残るのが求めたい最大の素因数になる。そして素因数ではない数字は必ず 自分より小さい素因数で構成されている という話もあるので、素因数に拘らず単純に小さい数字から順番に割り切れるかをチェックしていけば良さそう(それが素因数かどうかをチェックするより簡単)

例えば 1400 の場合、

  • 1400 / 2 → 割り切れる
  • 1400 / 2 = 700 (21 * 700)
  • 700 / 2 → 割り切れる
  • 700 / 2 = 350 (22 * 350)
  • 350 / 2 → 割り切れる
  • 350 / 2 = 175 (23 * 175)
  • 175 / 2 → 割り切れない
  • 175 / 3 → 割り切れない
  • 175 / 4 → 割り切れない
  • 175 / 5 → 割り切れる
  • 175 / 5 = 35 (23 * 51 * 35)
  • 35 / 5 → 割り切れる
  • 35 / 5 = 7 (23 * 52 * 7)
  • 7 / 5 → 割り切れない
  • 7 / 6 → 割り切れない
  • 7 / 7 → 割り切れる
  • 7 / 7 = 1 (23 * 52 * 7)

これで最大の素因数は 7 と分かる。これをコードで表現する。

Solution

# https://projecteuler.net/problem=3

num = 600851475143
divisor = 2

while num > divisor:
    while (num % divisor == 0):
        num = num // divisor
    divisor += 1

print(num)

今日の学び

やはり素因数分解自然数を分析する強力なツールだ。

Even Fibonacci Numbers, Project Euler Problem 2

https://projecteuler.net/problem=2

みんな大好きフィボナッチ数。4,000,000以下で、かつ2で割り切れるフィボナッチ数を全部足せという問題。

フィボナッチ数の公式はこの間数学ガールで見たけど、自力で導けない公式は使わない自分ルールがあるので愚直に足し込む作戦でいく。

Solution 1

# https://projecteuler.net/problem=2

a, b = 1, 2
sum = 0

while b < 4_000_000:
    if b % 2 == 0:
        sum += b
    a, b = b, a + b

print(sum)

Solution 2

再帰関数 Ver. も書いた。Pythonistaだとあからさまに遅くなる。それも学び。

# https://projecteuler.net/problem=2

def fib(n: int) -> int:
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return fib(n - 2) + fib(n - 1)

n = 1
fib_num = fib(n)
sum = 0

while fib_num < 4_000_000:
    if fib_num % 2 == 0:
        sum += fib_num
    n += 1
    fib_num = fib(n)

print(sum)

今日の学び(Python)

  • 代入は複数同時にできる
  • スワップa, b = b, a
  • 数値リテラル_ をセパレーターにできる
  • Pythonistaの再帰関数は遅い

Multiples of 3 and 5, Project Euler Problem 1

https://projecteuler.net/problem=1

1000より小さい3の倍数と5の倍数を全て足せという問題。数学的アプローチなら等差数列の和の公式を使えばよさそう。ただし両方の和を単純に足すと3×5=15の倍数分が重複するので注意。

Pythonの勉強も兼ねるのでまずはloop文書いて愚直に足し込んでみる。とりあえずfor文どうやって書くんだっけ?でドキュメント眺めるところからスタート(Pythonistaは公式ドキュメントにすぐアクセスできるのでエラい!)。An Informal Introduction 眺めてるとrange関数を使えば簡単そう!ってことで書いてみる。

Solution 1

# https://projecteuler.net/problem=1

sum = 0
for n in range(3, 1000, 3):
  sum += n
for n in range(5, 1000, 5):
  if n % 3 != 0:
    sum += n
print(sum)

Solution 2

等差数列の和の公式Ver.

# https://projecteuler.net/problem=1

def sum_multiples(diff, limit = 999):
    # n * (p(1) + p(n)) / 2
    nth_num = limit - limit % diff
    n = nth_num // diff
    return n * (diff + nth_num) // 2
        
result = sum_multiples(3) + sum_multiples(5) - sum_multiples(15)
print(result) 

今日の学び(Python)

  • 四則演算は +-*/
  • int 同士の +-* は int を返すが / は float
  • int を返す除算は //
  • 剰余演算は %
  • 乗数は **
  • for, while, if 文の末尾に : コロン必要
  • 関数定義 def 文の末尾にも : コロン必要