https://projecteuler.net/problem=10 200万以下の素数を求めて全て足す問題。 ある数nが素数かどうかチェックする素朴な方法「√n 以下で割り切れる素数があれば素数ではない、なければ素数」を実装した。 primes = [] def is_prime(n): for p in primes: if n % p == 0: return False if p ** 2 > n: break primes.append(n) return True sum = 0 for n in range(2, 2_000_000): if is_prime(n): sum += n if n % 10000 == 0: print(n, len(primes)) print(sum)
https://projecteuler.net/problem=9 以下条件を全て満たす a, b, c で、 a < b < c a + b + c = 1000 a^2 + b^2 = c^2 その時の a * b * c を求める問題。 for a in range(1, 334): for b in range(a + 1, (1000 - a) // 2): c = 1000 - a - b if a ** 2 + b ** 2 == c ** 2: print(a, b, c) print(a * b * c)
https://projecteuler.net/problem=8 文字列中のパターン探索。1000桁の数字で連結する13桁の数字をそれぞれ掛けて最大になるパターンを探索する。 num_1000_d = """ 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450 """.replace("\n", "") def product(num_str): result = 1 for n in num_str: result *= int(n) return result # test print(product("9989")) # 5832 def max_product(num_str, d): if len(num_str) < d: return 0 max_p = 0 for i in range(len(num_str) - d + 1): p = product(num_str[i:i+d]) max_p = max(max_p, p) return max_p # test print(max_product(num_1000_d, 4)) # 5832 print(max_product(num_1000_d, 13)) # ? ...
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. ...
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)) # ?
https://projecteuler.net/problem=5 1から20全ての数で割り切れる最小の数を求める問題。「割り切れる」という性質と素因数分解を考えると解決の糸口が見つけられた。例えば20で割り切れるとは、 20 × a = 2^2 × 5^1 × a つまり素因数として2が2つ以上、5が1つ以上含まれている数。同様に16で割り切れる数は、 16 × b = 2^4 × b 20でも16でも割り切れる最小の数は2が4つ、5が1つのみ素因数として含まれていればよいので、 2^4 × 5^1 = 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. ...
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. ...
https://projecteuler.net/problem=3 与えられた数字の最も大きい素因数を求める問題。素因数を小さい順に出していって、その数字で割り切れるかをチェックすればいい？と最初考えたが計算効率が悪そう。しばらく考える。 そういえば最近数学ガールで読んだ「全ての自然数は素数の積の形で一意に表現できる」っていうのを思い出す。 n = 2^a * 3^b * 5^c * … つまり小さい素因数を順番に除算で取り除いていけば最後に残るのが求めたい最大の素因数になる。そして素因数ではない数字は必ず 自分より小さい素因数で構成されている という話もあるので、素因数に拘らず単純に小さい数字から順番に割り切れるかをチェックしていけば良さそう(それが素因数かどうかをチェックするより簡単) 例えば 1400 の場合、 1400 / 2 → 割り切れる 1400 / 2 = 700 (2^1 * 700) 700 / 2 → 割り切れる 700 / 2 = 350 (2^2 * 350) 350 / 2 → 割り切れる 350 / 2 = 175 (2^3 * 175) 175 / 2 → 割り切れない 175 / 3 → 割り切れない 175 / 4 → 割り切れない 175 / 5 → 割り切れる 175 / 5 = 35 (2^3 * 5^1 * 35) 35 / 5 → 割り切れる 35 / 5 = 7 (2^3 * 5^2 * 7) 7 / 5 → 割り切れない 7 / 6 → 割り切れない 7 / 7 → 割り切れる 7 / 7 = 1 (2^3 * 5^2 * 7) これで最大の素因数は 7 と分かる。これをコードで表現する。 ...
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の再帰関数は遅い
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 文の末尾にも : コロン必要