Smallest multiple, Project Euler Problem 5

February 27, 2020

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.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]