素因数分解・素数判定

整数を素因数分解して「2^3 × 3^2 × 5」の形で出します。素数かどうか、約数の個数と一覧も表示。24桁未満の正の整数に対応し、結果は掛け戻して元の数に戻ることを確かめています。

読み込み中…

次におすすめ

この結果のあとは、最大公約数・最小公倍数で 2〜10個の整数。互除法の手順つき。

次は「最大公約数・最小公倍数」を使う

このほかに、この結果に関連するツール

使い方と仕様

整数を入れて「分解する」を押すと、素因数分解を「2^3 × 3^2 × 5」の形で出します。同時に、素数かどうか、約数の個数、約数の一覧(小さい順)を出します。全角の数字や、桁区切りのカンマ・空白(1,000,000 など)も読みます。

扱えるのは 1 以上 24 桁未満(10^24 未満)の整数です。0・負の数・小数・指数表記は分解しません。0 は「どの数でも割り切れる」ので素因数が決まらず、負の数は絶対値を入れてもらう扱いにしています。1 は素数でも合成数でもなく、素因数を持ちません(約数は 1 だけ)。

分解の方法は、まず小さい数(20000 未満)で順に割り、残った数を Miller-Rabin 法で素数かどうか判定します。合成数なら Pollard の rho 法で因数を探して、再び同じ手順で分けていきます。24桁未満では、使っている 13 個の底による Miller-Rabin 判定で結果が確定します(素数判定に確率的な誤りはありません)。10^12 付近の素数2つの積のような、もっとも手間のかかる場合でも、通常は1秒もかかりません。

まれに反復の上限(600万回)に達して分解しきれないときは、残った数を「未分解」として示し、素数かどうかの判定や約数は出しません。この場合も、見つかった素因数と未分解の数を掛け戻すと、元の数になります。

約数の一覧は、個数が 5000 個以下のときだけ出します。それより多いときは、個数だけを出します(一覧は、素因数の指数から計算するので、個数は常に求められます)。約数の個数は、各素因数の(指数 + 1)をすべて掛けた数です。360 = 2^3 × 3^2 × 5 なら 4 × 3 × 2 = 24 個です。

計算はすべてお使いのブラウザの中で行い、入力した数は送信されません。暗号の鍵を分解する用途や、公開された巨大な数の記録に挑むようなものは対象外です。

よくある質問

素因数分解の答えは1通りですか。
素因数を並べる順番を除けば、1通りです。このツールは小さい順に並べて、同じ素数は「2^3」のように指数でまとめます。
1 は素数ですか。
素数ではありません。1 は素数でも合成数でもない数として扱います。2 以上で、1 と自分自身以外に約数を持たない数が素数です。
素数かどうかだけ知りたいときはどうしますか。
数を入れると、結果の上に「素数です」または「素数ではありません」と出ます。素数でないときは、そのまま素因数分解の結果も見られます。
何桁の数まで分解できますか。
24桁未満(10^24 未満)までです。それ以上は、素数判定の確定する範囲と、画面が固まらない時間を考えて、受け付けません。
約数が多すぎて一覧が出ないのはなぜですか。
約数が 5000 個を超えると、画面に並べきれないので、個数だけを出します。個数は素因数の指数から求めています。
入力した数は、どこかに送られますか。
送られません。計算はすべてお使いのブラウザの中で行います。

お金・計算ツール

お金・計算ツールを一覧で見る(31)