Project Eulerの初心者向け問題をPythonで解く
はじめに
Project Eulerは、プログラミングによって解くことを意図した数学的な問題を集めたウェブサイトです。2024年3月24日現在873問が掲載されており、簡単な問題から非常に困難な問題までバラエティ豊かな問題が集められているため、プログラミングの初級者から上級者まで楽しむことができます。この記事では、ウェブサイトの基本的な使い方と初心者向けの最初の5問について解説します。
Project Eulerウェブサイトの使い方
このウェブサイトはすべて英語表記ですが、文章は平易で直感的に理解できる内容になっているので、使い方でつまずくことはないと思います。
始めて利用する場合には、表示されたメニューバーのRegisterをクリックして、ユーザ名(Username)とパスワード(Password)を登録します。二回目以後は、メニューバーのSign Inをクリックします。サインインした状態で表示されるメニューバーのAccountをクリックすると、ユーザ名とパスワードを変更できます。また、Recovery Keyを生成しておくと、ユーザ名とパスワードのいずれかを忘れた場合にもアカウントを回復できます。
メニューバーのArchivesをクリックすると問題の一覧が表示され、タイトルをクリックすると問題内容のページが表示されます。サインインした状態では、問題の一覧に難易度が付加され、問題内容のページに解答(Answer)を入力するフォームが表示されます。フォームに入力した解答が正しければ解答日時が登録され、他の人が投稿した解答を見て自身のプログラムを改良するためのヒントを得られるようになります。また、自身の解答状況はメニューバーのProgressで確認できます。
問題は原則として易しいものから順に並んでいるので、自身の実力に合った問題を選んで解くことができます。問題を解く際には、どのようなプログラミング言語と手段を使っても構わないのですが、１分以内の実行時間で解けるようにプログラミングすることが推奨されています。従って、力ずく(Brute Force)でプログラムを書くのではなく、数学的な規則性、アルゴリズムの計算量、コードの効率性などを考慮することが重要になります。
以下、最初の5問について内容とPythonによる解法について解説していきます。解法の部分はネタバレになっていますので、興味のある方はご自身で問題を解いた後に読んでいただくとよいと思います。
問題#1 Multiples of 3 or 5 (3または5の倍数)
原文:
If we list all the natural numbers below
Find the sum of all the multiples of
和訳:
10未満の自然数で3または5の倍数を並べると 3, 5, 6, 9 であり、これら倍数の和は 23 である。
1000未満の3または5の倍数の和を求めよ。
解法:
この問題は、数列の和の公式を使うことにより手計算で解くこともできますが、ここではPythonのプログラムで解くことにします。
def multiple3or5(stop=10):
"""3または5の倍数の和を求める
Parameter int stop: 自然数の範囲 [1-stop)
Returns int sum: 3または5の倍数の和
"""
sum = 0
for n in range(1, stop):
if n % 3 == 0 or n % 5 == 0:
sum += n
return sum
print('Answer:', multiple3or5(10)) # Answer: 23
print('Answer:', multiple3or5(1000))
問題に書かれている条件を素直にコードに変換しただけなので、特に説明が必要な事項はないと思います。一点だけ補足すると、「10未満の自然数では答えが23になる」というヒントがあるので、これを確認できるような関数にしてあります。
問題#2 Even Fibonacci Numbers (偶数のフィボナッチ数)
原文:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
和訳:
フィボナッチ数列の新しい各項は、直前の2項の和によって生成される。1 と 2 から始めると、最初の10項は、
項の値が400万までのフィボナッチ数列の項において、偶数の項の和を求めよ。
解法:
この問題も、フィボナッチ数列の生成過程を素直にコード化すれば解くことができます。
def even_fibonacci(stop=100):
"""偶数のフィボナッチ数の和を求める
Parameter int stop: フィボナッチ数の範囲 [1-stop)
Returns int sum: 偶数のフィボナッチ数の和
"""
sum = 0
cur = 1 # 現在の値
next = 2 # 次の値
while next < stop:
# print(next, end=',') # フィボナッチ数列
if next % 2 == 0:
sum += next
cur, next = next, cur + next
return sum
print('Answer:', even_fibonacci(100)) # Answer: 44
print('Answer:', even_fibonacci(4_000_000))
なお、フィボナッチ数列で偶数の項は3回ごとに現れますが、これを考慮するとかえって処理が複雑になるため、毎回偶数の判定をしています。
問題#3 Largest Prime Factor (最大の素因数)
原文:
The prime factors of
What is the largest prime factor of the number
和訳:
13195 の素因数は、5, 7, 13, 29 である。
600851475143 の最大の素因数は何か？
解法:
単純には、素数のリストを作って、大きなものから順に因数になっているか判定すれば解が求まると考えらえますが、素数のリストを作るコストはかなり大きくなります。この問題を回避するため、小さな因数を順に見つけて元の数値を割ってゆき、最後に残った因数が最大の素因数となるようにします。
def largest_prime(target=13195):
"""最大の素因数を求める
Parameter int target: 分解対象
Returns int factor: 最大の素因数
"""
factor = 2 # 因数候補
while target > factor:
if target % factor == 0:
target //= factor
# print(factor, end=',') # 素因数
else:
factor += 1
return factor
print('Answer:', largest_prime(13195)) # Answer: 29
print('Answer:', largest_prime(600851475143))
上記のプログラムは、元の数値が大きくかつ因数が少ない場合に時間がかかりますが、幸いにもこの問題は一瞬で解くことができます。Project Eulerでは問題が解ければよいので、問題に応じた適切な方法を見つけることが重要です。
問題#4 Largest Palindrome Product (最大の積の回文数)
原文:
A palindromic number reads the same both ways. The largest palindrome made from the product of two
Find the largest palindrome made from the product of two
和訳:
回文数は左右どちらから読んでも同じになる数である。二つの2桁数の積で求められる最大の回文数は
二つの3桁数の積で求められる最大の回文数を求めよ。
解法:
回文数に関する問題は、今後もいくつか出てきます。そこで、回文数かどうかを判定する関数を作っておきます。あとは二つの数値の組み合わせを順にチェックしていくことによって解を見つけます。
def largest_palindrome(digit=2):
"""最大の積の回文数を求める
Parameter int digit: 桁数
Returns int palindrome: 最大の回文数
"""
min = 10 ** (digit - 1) # digit桁の最小数
max = min * 10 - 1 # digit桁の最大数
palindrome = 0 # 回文数
for n1 in range(max, min, -1):
for n2 in range(max, min, -1):
p = n1 * n2
if is_palindrome(p) and p > palindrome:
# print(n1, n2, p)
palindrome = p
elif p < palindrome:
break
return palindrome
def is_palindrome(n):
"""回文数かどうか判定する
Parameter int n: 自然数
Returns bool: 回文数ならばTrue
"""
s = str(n)
return s == s[::-1]
print('Answer:', largest_palindrome(2)) # Answer: 9009
print('Answer:', largest_palindrome(3))
最大の積が解となるなので、for文は数値が大きな方から試していき、解の可能性がなくなったらbreak文で打ち切ることにより高速化を図っています。
問題#5 Smallest Multiple (最小の積)
原文:
What is the smallest positive number that is evenly divisible (divisible with no remainder) by all of the numbers from
和訳:
2520 は 1 から 10 までの各数で余りなしに割ることができる最小の数である。
1 から 20 までのすべての数で割り切れる（余りなしに割ることができる）最小の正の数は何か？
解法:
この問題の解き方はいろいろ考えられますが、今回は最小公倍数と最大公約数の関係を利用します。すなわち、二つの整数を
この計算を繰り返すことにより、すべての数で割り切れる最小の数を求めることができます。なお、最大公約数の計算にはユークリッドの互除法を使います。
def smallest_multiple(upper=10):
"""最小の公倍数を求める
Parameter int upper: 除数の範囲 [1, upper]
Returns int multiple: 最小の公倍数
"""
multiple = 1
for n in range(2, upper + 1):
d = gcd(n, multiple)
multiple *= (n // d)
# print(multiple, end=',')
return multiple
def gcd(n, m):
"""最大公約数を求める（ユークリッドの互除法）
Parameters int n, int m: 自然数
Returns int gcd: 最大公約数
"""
while True:
if m > n:
n, m = m, n
else:
n %= m
if n == 0:
return m
print('Answer:', smallest_multiple(10)) # Answer: 2520
print('Answer:', smallest_multiple(20))
階乗の計算結果は桁数が多くなりがちですが、最大公約数で割りながら計算を進めることにより桁数の増加を抑制しています。
おわりに
Project Eulerの最初の5問について紹介しました。多くの方にとっては簡単な問題だったかもしれません。実際、ウェブサイトに登録されている最初の50問は難易度が最も低く(Dificulty rating: 5%)、ウオーミングアップの位置づけです。51問目以降に難易度が高い問題が登場するようになるので、自信のある方はそこから始めるのがよいと思います。
Discussion