Project Euler 1~5をpythonで解く

すでにProject EulerのProblem37まで解いているので、そこまでの問題を自分がどう解いたか記事にしていく。

Problem 1

8/5日に挑戦。

問題（英語）

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

( https://projecteuler.net/problem=1 )

問題（日本語）

10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.

同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.

（ http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201 ）

コード

Top = 1000
mul_3or5 = [i for i in range(1,Top) if i % 3 == 0 or i % 5 == 0]
result = sum(mul_3or5)
print(result)

Top = 1000

mul_3or5 = [i for i in range(1,Top) if i % 3 == 0 or i % 5 == 0]

result = sum(mul_3or5)

print(result)

考え方

最初の問題だけに簡単。

基本的に問題の文章をそのまま実行しただけ。

以前勉強したリスト内包表記を使ってみた。

わざわざなぜ変数mul_3or5に入れてからsumをしたのかは謎である。

Problem 2

問題（英語）

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

（ https://projecteuler.net/problem=2 ）

問題（日本語）

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

（ http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202 ）

コード

#num1,num2を足して行って、偶数ならsumに足す。
num1=1
num2=2
sum = 0
Top = 4000000
while num2 <= Top:
    if num2 % 2 == 0:
        sum += num2
    copy = num1
    num1 = num2
    num2 += copy
print(sum)

#num1,num2を足して行って、偶数ならsumに足す。

num1=1

num2=2

sum = 0

Top = 4000000

while num2 <= Top:

if num2 % 2 == 0:

sum += num2

copy = num1

num1 = num2

num2 += copy

print(sum)

考え方

みんな大好きフィボナッチ数列。

コード中のコメントに書いてある通り。

num1 < num2 として更新していく。

num1をnum2で上書きする際にcopyに記録しておく。

ただ、

(num1,num2) = (num2,num1+num2)

1	(num1,num2) = (num2,num1+num2)

と書く方がシンプルだった。

Problem 3

問題（英語）

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

（ https://projecteuler.net/problem=3 ）

問題（日本語）

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

（ http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203 ）

コード

#試し割算
n = 600851475143
a = 2
while a * a <= n:
    while n % a == 0:
        n //= a
        max_fct = a
    a += 1
if n > 1:
    max_fct = n
print(max_fct)

#試し割算

n = 600851475143

a = 2

while a * a <= n:

while n % a == 0:

n //= a

max_fct = a

a += 1

if n > 1:

max_fct = n

print(max_fct)

考え方

試し割り算についてネットのどこかの記事を参考にしたような気がするがメモしてなかった。

（途中から参考にしたサイトをメモするようになった）

最後の

if n > 1:

if n > 1:

の説明が難しいが、n = 1の時は順当に max_fct = aだけど、そうでない時は、max_fact = nになるという意味である。

これはa*a<=nの範囲までしか計算してないからで、例えば21 = 3*7は5*5>25なのでa=4までしか割らない。

そして、n=7として残った数が最大の素因数となる。

Problem 4

問題（英語）

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

( https://projecteuler.net/problem=4 )

問題（日本語）

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.

では, 3桁の数の積で表される回文数の最大値を求めよ.

( http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204 )

コード1

#答えは906609=993*913
#nが回文数ならTrueを返す関数
def is_palindrome(n):
    #数字を1桁ごとに分解したリスト
    digits = [int(c) for c in str(n)]
    length = len(digits)
    if length % 2 == 0:
        for x in range(length // 2):
            judg = (digits[x] == digits[length-x-1])
            if judg == False:
                return(False)
        return(True)
    else:
        for x in range((length-1) // 2):
            judg = (digits[x] == digits[length-x-1])
            if judg == False:
                return(False)
        return(True)

max_pal = 9009
for num1 in range(100,1000):
    for num2 in range(100,1000):
        if num2 > num1:
            break
        num3 = num1 * num2
        if is_palindrome(num3):
            max_pal = max([max_pal,num3])
print(max_pal)

#答えは906609=993*913

#nが回文数ならTrueを返す関数

def is_palindrome(n):

#数字を1桁ごとに分解したリスト

digits = [int(c) for c in str(n)]

length = len(digits)

if length % 2 == 0:

for x in range(length // 2):

judg = (digits[x] == digits[length-x-1])

if judg == False:

return(False)

return(True)

else:

for x in range((length-1) // 2):

judg = (digits[x] == digits[length-x-1])

if judg == False:

return(False)

return(True)

max_pal = 9009

for num1 in range(100,1000):

for num2 in range(100,1000):

if num2 > num1:

break

num3 = num1 * num2

if is_palindrome(num3):

max_pal = max([max_pal,num3])

print(max_pal)

コード2(改)

#答えは906609=993*913
#nが回文数ならTrueを返す関数
def is_palindrome(n):
    #数字を1桁ごとに分解したリスト
    digits = [int(c) for c in str(n)]
    import copy
    digits_copy = copy.deepcopy(digits)
    digits.reverse()
    if digits == digits_copy:
        return(True)
    else:
        return(False)

max_pal = 9009
for num1 in range(100,1000):
    for num2 in range(100,1000):
        if num2 > num1:
            break
        num3 = num1 * num2
        if is_palindrome(num3):
            max_pal = max([max_pal,num3])
print(max_pal)

#答えは906609=993*913

#nが回文数ならTrueを返す関数

def is_palindrome(n):

#数字を1桁ごとに分解したリスト

digits = [int(c) for c in str(n)]

import copy

digits_copy = copy.deepcopy(digits)

digits.reverse()

if digits == digits_copy:

return(True)

else:

return(False)

max_pal = 9009

for num1 in range(100,1000):

for num2 in range(100,1000):

if num2 > num1:

break

num3 = num1 * num2

if is_palindrome(num3):

max_pal = max([max_pal,num3])

print(max_pal)

考え方

見苦しいコードですみません...。

やってることは3桁×3桁をfor文で回して回文数か判定し、現在の最大より大きければ更新していくというシンプルなもの。

回文数かどうかの判定をどう表現するかに悩んだ。

つい先日やったProblem36でも回文数が出てきて、この時に使った下の判定方法が一番シンプルかと思う。

if s == s[::-1]:
    return True

1 2	if s == s[::-1]: return True

ここの「s」はstr型である。

この頃はスライスに慣れてなかったのと、str型が意外と便利ということを知らなかったので長く分かりづらいコードになってしまった。

Problem 5

問題（英語）

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

（ https://projecteuler.net/problem=5 ）

問題（日本語）

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

( http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205 )

コード

なし

考え方

コードで書いたら処理に時間がかかりすぎて分からなかったので、自力で解いた。

結果から言うと、答えは232792560で、これは次の計算から得られる。

232792560 = 2*3*5*7*11*13*17*19*(2^3)*(3^1)

素数の分と、最後のは同じ素因数を複数個持つもの、つまり16=2^4と9=3^2の余剰分をかけたものである。

あれ？

今になってよくよく考えてみるとこれ1~20の最小公倍数を求める問題だった笑。

最大公約数は再帰関数を使って求められるみたいで、2数の最少公倍数は2数の積を最大公約数で割った値になるみたい。

ここら辺を使えばコードで書けそうだが、今日はここまで記事を書くだけで疲れたのでまた後で書いてみる。

追記

割と簡単に書けた。

#参考「https://www.planeta.tokyo/entry/3732/」複数の最少公倍数
def gcd(a,b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b

def lcm(a,b):
    return a * b // gcd(a,b)

def main():
    N = 20
    #1~20のリスト
    ls = list(range(1,N+1))
    ans = ls[0] #1
    for i in range(1,N):
        ans = lcm(ans,ls[i])
    print(ans) #232792560

main()

#参考「https://www.planeta.tokyo/entry/3732/」複数の最少公倍数

def gcd(a,b):

if a < b:

a, b = b, a

while a % b != 0:

a, b = b, a % b

return b

def lcm(a,b):

return a * b // gcd(a,b)

def main():

N = 20

#1~20のリスト

ls = list(range(1,N+1))

ans = ls[0] #1

for i in range(1,N):

ans = lcm(ans,ls[i])

print(ans) #232792560

main()

gcdとlcmはそれぞれ「Greatest Common Divisor（最大公約数）」、「Least Common Multiple（最小公倍数）」の略である。

gcdはユークリッド互除法で求めて、lcmはgcdを用いて求める。

N個の最小公倍数は、2数をまず求めて、その最小公倍数と1つの最小公倍数を求めて、とN-1回繰り返せば良い。

追記ここまで。

以上！

まだ1ヶ月しか経ってないけど、やはりこうやって最初の頃のコードを見ていると成長を感じる...。

出来るだけ早めにProblem37までの記事を書いちゃいます。

次の記事→「 Project Euler 6~10をpythonで解く」