Project Euler

Project Euler problem #001 Multiples of 3 and 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.
　
問題1：1000未満の3または5の倍数の和を求めよ。
　
forループを使っていくのが自然かな。

# forループとif
limit = 1000
result = 0
for i in range(limit):
    if i%3 == 0 or i%5 ==0:
        result += i
print(result)

　
ifの部分は３項演算子でも。

# forループと3項演算子
limit = 1000
result = 0
for i in range(limit):
    result += i if i%5 == 0 or i%3 ==0 else 0
print(result)

　
リスト内包表記を使うとシンプルに。

# リスト内包表記
limit = 1000
result = sum([x for x in range(limit) if x%3 == 0 or x%5 ==0 ])
print(result)

　
3つの等差数列に分けても。

# 等差数列のsum()
limit = 1000
result = sum(range(0, limit, 3)) + sum(range(0, limit, 5)) - sum(range(0, limit, 15))
print(result)

　
等差数列の和の公式を使うと、コードは複雑になるけど処理時間は大幅短縮。

# 等差数列の和の公式
limit = 1000
def sum_multi(x):
    first = x
    last = (limit - 1) - (limit - 1) % x 
    return int((first + last) * (last / x) / 2)
result = sum_multi(3) + sum_multi(5) - sum_multi(15)
print(result)

Project Euler problem #002 Even Fibonacci numbers

　
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.
　
問題2：フィボナッチ数列で400万以下の偶数の項の和を求めよ。
　

def fib4():
    a, b = 0, 1
    result = 0
    while b < 4*10**6:
        result += b if b % 2 ==0 else 0
        a, b = b, a + b
    return result

print(fib4())
# 4613732

　
フィボナッチ数列の偶数項は3項ごとに登場。
それと、フィボナッチ数列の生成をlambda式で1行にまとめてみると、

f = lambda x:int(((1 + 5**0.5) / 2)**i / 5**0.5 + 0.5)
i, result = 3, 0
while f(i) < 4*10**6:
    result += f(i)
    i += 3
print(result)

Project Euler problem #003 Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
　
問題3：600851475143の素因数のうち最大のものを求めよ。
　

# 素数のジェネレータ
def gen2(start=2, stop=1000000):
    pr = max(1, start - 1)
    while True:
        while pr < stop:
            pr += 1
            if all(pr%x != 0 for x in range(2, int(pr**0.5) + 1)):
                break
        yield pr

# 素因数分解
def factorial(n):
    if n in [0, 1]:
        return [n]
    result = []
    stop = int(n**0.5) + 1
    g = gen2()
    pr = next(g)
    while pr < stop:
        if n % pr == 0:
            result.append(pr)
            n //= pr
            continue
        pr = next(g)
    if n > 1:
        result.append(n)
    return result

print(max(factorial(600851475143)))
# 6857

Project Euler problem #004 Largest palindrome product

　
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.
　
問題：3桁の2つの数の積で作った回文のうち最大のものを求めよ。
　
forループを2重にして回文判定するとよさそう。

result = 0
for i in range(100, 1000):
    for j in range(i, 1000):
        if str(i * j) == str(i * j)[::-1]:
            result = max(result, i * j)
print(result)
# 906609

　
端が9と仮定すると、奇数×奇数なので、forループは奇数で。　

result = 0
for i in range(901, 1000, 2):
    for j in range(i, 1000, 2):
        if str(i * j) == str(i * j)[::-1]:
            result = max(result, i * j)
print(result)

　
積の1の位が9になるのは1×9、3×3、7×7、9×1なので、さらにループを減らせそう。

result = 0
pair9 = {1:8, 3:0, 7:0, 9:2}
for i in range(901, 1000, 2):
    if i%10 in pair9:                  # 1の位が1,3, 7, 9なら
        incre = pair9[i%10]            # 相手の1の位が決まる
    else:
        continue
    for j in range(i+incre, 1000, 10): # 1の位は固定なのでstep=10
        if str(i * j) == str(i * j)[::-1]:
            result = max(result, i * j)
print(result)

Archived Problems - Project Euler