Help us understand the problem. What is going on with this article?

試し割り法による素因数分解

概要

素因数(prime factor)とは、ある自然数の約数となる素数のことです。また素因数分解 (prime factorization) とは、自然数を素因数の積の形で表すことを指します。例えば360を素因数分解すると、$2^3$ × $3^2$ × $5^1$と表すことができます。本記事では2以上の自然数の素因数を試し割り法で列挙する手法を紹介します。

方針

基本的な考え方としては、与えられた2以上の自然数nに対して、nより小さい数で割り切れるかどうかを順番に確かめることで素因数判定を行っていきます。nを割り切る素因数を見つけた際、その素因数の累乗でも割り切れるかどうかも同時に確認しておくと効率的です。素因数候補として確かめるべき値の範囲は、2以上$\sqrt{n}$以下で十分です。

実装例

# Return a list of the prime factors for a natural number bigger than 1
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi(の累乗)で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

n = int(input())
print(trial_division(n))

実行結果

# 入力
12
# 出力
[2, 2, 3]

# 入力
100
# 出力
[2, 2, 5, 5]

# 入力
600851475143
# 出力
[71, 839, 1471, 6857]

参考

試し割り法(Wikipedia)
Pythonで素因数分解(試し割り法)
Pythonで競技プログラミング 〜基本的なアルゴリズム 〜
[Python]試し割法で素因数分解する

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away