Largest prime factor, Project Euler Problem 3

February 23, 2020

与えられた数字の最も大きい素因数を求める問題。素因数を小さい順に出していって、その数字で割り切れるかをチェックすればいい？と最初考えたが計算効率が悪そう。しばらく考える。

そういえば最近数学ガールで読んだ「全ての自然数は素数の積の形で一意に表現できる」っていうのを思い出す。

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 と分かる。これをコードで表現する。

Solution #


# https://projecteuler.net/problem=3

num = 600851475143
divisor = 2

while num > divisor:
	while (num % divisor == 0):
		num = num // divisor
	divisor += 1

print(num)

今日の学び #

やはり素因数分解は自然数を分析する強力なツールだ。