CalcOpenly
日本語

素因数分解計算機

Prime factorization of any whole number up to 60 digits, with a factor tree, a prime or composite verdict, its divisors and the nearest primes.

更新日 検証済みの例：6

Up to 60 digits. Expressions work too, e.g. 2^67 − 1.
試す
Prime factorization
2³ × 3² × 5
Prime factorization: 2³ × 3² × 5
Prime or composite
Composite
Number of divisors
24
Sum of divisors σ(n)
1,170
Previous prime
359
Next prime
367

360 = 2³ × 3² × 5, so it is composite with 24 divisors adding up to 1170. The nearest primes are 359 and 367.

Factor tree

360218029024531535
Divisor pairs 行数：12
DivisorPaired divisor n ÷ d
1360
2180
3120
490
572
660
845
940
1036
1230
1524
1820
計算方法 S

  1. Trial division by small primes

    divides by 2, 3\text{divides by } 2,\ 3

    Each prime is divided out as many times as it goes before moving on.

  2. Prime factorization

    360=23×32×5360 = 2^{3} \times 3^{2} \times 5

  3. Number of divisors

    d(n)=(3+1)(2+1)(1+1)=24d(n) = (3 + 1)(2 + 1)(1 + 1) = 24

  4. Sum of divisors

    σ(n)=24−12−1⋅33−13−1⋅52−15−1=1,170\sigma(n) = \frac{2^{4} - 1}{2 - 1} \cdot \frac{3^{3} - 1}{3 - 1} \cdot \frac{5^{2} - 1}{5 - 1} = 1{,}170

  5. Nearest primes

    359<360<367359 < 360 < 367

    Candidates are tested with the same Miller–Rabin check.

素因数分解計算機について

By the fundamental theorem of arithmetic, every whole number above 1 is a product of primes in exactly one way, apart from order: 360 = 2³ × 3² × 5. The calculator divides out primes below 10,000 by trial division, splits larger composite factors with Brent's version of Pollard's rho method, and proves each factor prime with a Miller–Rabin test on the first 13 prime bases, which is deterministic below 3.3 × 10²⁴ (Sorenson and Webster, 2015).

Simplifying fractions and radicals, finding common denominators, and number puzzles all start from a factorization. The exponents also count the divisors: 360 has (3 + 1)(2 + 1)(1 + 1) = 24 divisors that sum to 1,170, and the nearest primes are 359 and 367.

Numbers up to 60 digits are accepted, including expressions such as 2^67 − 1. Above 3.3 × 10²⁴ a prime verdict is labeled “probable prime”, with an error chance below 4⁻²⁰.

計算例

360

Whole number
360
Prime factorization
2³ × 3² × 5
Prime or composite
Composite
Number of divisors
24
Sum of divisors σ(n)
1,170
Previous prime
359
Next prime
367

照合元：Python 3.8 trial division and divisor enumeration (scratchpad forkA/verify.py)

Project Euler problem 3

Whole number
600851475143
Prime factorization
71 × 839 × 1471 × 6857
Number of divisors
16

照合元：Project Euler #3 (largest prime factor 6857); product and primality checked in Python 3.8

Cole's factorization of 2^67 − 1

Whole number
2^67-1
Prime factorization
193707721 × 761838257287
Prime or composite
Composite
Number of divisors
4

照合元：F. N. Cole, 1903 (Bull. AMS 10:134); product and primality of both factors checked by Python trial division

97 is prime

Whole number
97
Prime factorization
97
Prime or composite
Prime
Number of divisors
2
Sum of divisors σ(n)
98
Previous prime
89
Next prime
101

照合元：Table of primes (OEIS A000040): 89, 97, 101

よくある質問

How do you find the prime factorization of a number?

Divide by the smallest prime that goes in, and repeat on the quotient until it reaches 1. For 360: 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45, ÷ 3 = 15, ÷ 3 = 5, and 5 is prime, so 360 = 2³ × 3² × 5. Only primes up to the square root of what is left need testing; if none divides it, the remainder is itself prime.

Is 1 a prime number?

No. A prime has exactly two divisors, 1 and itself, and 1 has only one. Excluding 1 keeps factorizations unique: if 1 counted as prime, 6 could be written as 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 and so on. 1 is neither prime nor composite, and 2 is the smallest prime and the only even one.

How do you find the number of divisors from the prime factorization?

Add 1 to each exponent and multiply. 360 = 2³ × 3² × 5¹, so it has (3 + 1)(2 + 1)(1 + 1) = 24 divisors, because each divisor uses 0 to 3 twos, 0 to 2 threes and 0 or 1 five. The sum of the divisors is a similar product: σ(360) = (2⁴ − 1)/1 × (3³ − 1)/2 × (5² − 1)/4 = 15 × 13 × 6 = 1,170.

How can you tell if a large number is prime?

Trial division up to √n is far too slow for 20-digit numbers, so the Miller–Rabin test checks a handful of bases instead. Below 3.3 × 10²⁴, passing with the first 13 primes (2 to 41) as bases proves primality (Sorenson and Webster, 2015). 2⁶¹ − 1 = 2,305,843,009,213,693,951 passes and is prime; 2⁶⁷ − 1 fails and equals 193,707,721 × 761,838,257,287.

Why does prime factorization matter in cryptography?

RSA encryption relies on multiplying two large primes being quick while factoring their product is impractically slow. NIST SP 800-57 rates a 2048-bit RSA modulus, about 617 decimal digits, as giving 112 bits of security. That is ten times the 60-digit limit here, and even within that limit Pollard's rho splits a number quickly only when one of its factors is fairly small.

「素因数分解計算機」の精度はどのくらいですか？

精度は入力値と計算方法の前提に依存します。十進演算には有効数字50桁を使いますが、推定、数値計算手法、元データの精度はそれより低い場合があります。表示の丸め処理でこれらの制約がなくなるわけではありません。 独立した出典の解答と照合した計算例：6。 例えば、「360」はPython 3.8 trial division and divisor enumeration (scratchpad forkA/verify.py)と照合しています。

この計算方法の出典は何ですか？

Hardy & Wright, An Introduction to the Theory of Numbers, §2.10 and §16.7 (divisor functions); Sorenson & Webster (2015), Strong pseudoprimes to twelve prime bases; Brent (1980), An improved Monte Carlo factorization algorithm.

この計算機について

n=p1e1p2e2⋯pkekd(n)=∏(ei+1)σ(n)=∏piei+1−1pi−1\begin{gathered} n = p_1^{e_1} p_2^{e_2}\cdots p_k^{e_k} \\[6pt] d(n) = \prod (e_i + 1) \\[6pt] \sigma(n) = \prod \frac{p_i^{e_i+1} - 1}{p_i - 1} \end{gathered}

出典

  1. Hardy & Wright, An Introduction to the Theory of Numbers, §2.10 and §16.7 (divisor functions)
  2. Sorenson & Webster (2015), Strong pseudoprimes to twelve prime bases
  3. Brent (1980), An improved Monte Carlo factorization algorithm

出典と照合済み

この計算機には、独立した出典の解答を使った計算例が 6 件あります。テストに組み込まれており、ここでも実行できます。

関連する計算ツール