アルゴリズムとデータ構造

素因数分解

どんな正の整数 n ≥ 2 も、素数の積として表すことができます。たとえば:
数値に対して素因数を求めることには多くの応用例があります。たとえば、その数の約数の個数を簡単に数えられたり、2つの数の最大公約数 (GCD) や最小公倍数 (LCM) を把握するときにも役立ったりします。
数 n (たとえば 300) を素因数の積として表すには、まず最小の素数 p (2) から始め、n が割り切れる限り繰り返し n を p で割ります (300 / 2 = 150, 150 / 2 = 75)。
その後、p を 1 ずつ増やして (p = 3)、再び n が割り切れるかを試します。割り切れるならば、可能な限り繰り返し n を割り続けます (75 / 3 = 25)。
次に p を再度 1 ずつ増やすと (p = 4)、もう二度と n は 4 で割り切れません。というのも、すでに 2 で割り切れるだけ割り尽くしているので、4 や 6、8 のように 2 の倍数になっている数ではこれ以上割り切ることができないためです。このアルゴリズムは最小の数から大きい数へと順に進むので、最終的に残った数については、すでに素数のみで割り尽くしていることが保証されます。
次のステップでは再び 1 だけ増やし (p = 5)、n が割り切れるかを調べます。今回の場合、75 / 5 = 5、さらに 5 / 5 = 1 となります。こうして割れるだけ割ったら、次へ進みます。そして p が よりも大きくなった時点でループを終えます。もしその時点で n が 1 より大きければ、残っている n 自体が素数として採用できます。
以上の手順で例の 300 は という形に表せます。
n = ...                              # n を素因数の積として表す
p, divisors, powers = 1, [], []      # prime factor, divisors, and their exponents

while p * p <= n:                    # p <= sqrt(n) の間繰り返す
    p += 1                           # 反復ごとに p を 1 ずつ増やす
    if n % p != 0:                   # n が p で割り切れないなら何もしない
        continue
    
    divisors.append(p)               # n % p == 0 => 素因数として p を追加
    powers.append(0)                 # 指数を 0 から始める
    while n % p == 0:                # 割り切れるだけ割り、
        n //= p
        powers[-1] += 1              # 割るたびに指数を 1 ずつ増加させる

if n > 1:                            # p > sqrt(n) の時点で n が 1 より大きいなら、
    divisors.append(n)               # n 自体が素数となるので追加
    powers.append(1)                 # 指数を 1 として追加

print(list(zip(divisors, powers)))   # 因数とその指数のペアを出力
各反復で、もし割り切れるなら対象の数を素因数で割り、そのたびに指数を 1 ずつ増やしていきます。
それでは、いくつかの数でアルゴリズムをシミュレーションしてみましょう。
n = 24
  1. p = 2, n = 24 (ループの最初に p を 1 から 2 へ増やした状態で始める) n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 12, powers = [1] n //= 2 ⇒ n = 6, powers = [2] n //= 2 ⇒ n = 3, powers = [3]
  1. p = 3, n = 3 ⇒ p * p = 9 は 2 より大きいので while ループを終了
  1. n > 1 ⇒ divisors = [2, 3], powers = [3, 1]
n = 75
  1. p = 2, n = 75
  1. p = 3, n = 75 n % 3 == 0 ⇒ divisors = [3], powers = [0] n //= 3 ⇒ n = 25, powers = [1]
  1. p = 4, n = 25
  1. p = 5, n = 25 n % 5 == 0 ⇒ divisors = [3, 5], powers = [1, 0] n //= 5 ⇒ n = 5, powers = [1, 1] n //= 5 ⇒ n = 1, powers = [1, 2]
  1. p * p > n ⇒ ループ終了 ⇒ divisors = [3, 5], powers = [1, 2]
n = 84
  1. p = 2, n = 84 n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 42, powers = [1] n //= 2 ⇒ n = 21, powers = [2]
  1. p = 3, n = 21 n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0] n //= 3 ⇒ n = 7, powers = [2, 1]
  1. p * p > n ⇒ ループ終了
  1. n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]
n = 31
  1. p = 2, n = 31
  1. p = 3, n = 31
  1. p = 4, n = 31
  1. p = 5, n = 31
  1. p = 6, n = 31
  1. p * p > n ⇒ ループ終了
  1. n > 1 ⇒ divisors = [31], powers = [1]

チャレンジ

整数 n が与えられたとき、その最大の素因数を求めてください。

入力

最初の行に整数 n が 1 つ与えられます (2 ≤ n ≤ )。

出力

n の最大の素因数を出力してください。

例

Input
Output
8
2
24
3
75
5
31
31
■ ボーナス: なぜ素数だけをチェックしないのか？
現在のアルゴリズムでは、2 から までのすべての数 (2, 3, 4, …) を試しますが、「それなら最初から素数だけを使って割り続ければいいのでは？」と思うかもしれません。
一見すると合理的に見えますが、実は までのすべての素数を先に求めようとすると、素数列挙に要する反復回数のほうが より多くなってしまうのがふつうです (正確には )。したがって、先に素数を列挙してからそのリストだけを使って割りまくる方法のほうが、かえって時間がかかることがあるのです。
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue