# 소인수분해 계산기

> 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.

직접 계산할 수 있는 페이지: https://www.calcopenly.com/ko/math/prime-factorization-calculator
분야: 수학 계산기

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⁻²⁰.

## 입력

- **Whole number**: Up to 60 digits. Expressions work too, e.g. 2^67 − 1.

## 결과

- Prime factorization — 주요 결과
- Prime or composite
- Number of divisors
- Sum of divisors σ(n)
- Previous prime
- Next prime

## 공식

$$
\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}
$$

## 계산 예제

### 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

### n = 1 (edge)

- Whole number: 1
- **Prime factorization: 1**
- **Prime or composite: Neither prime nor composite**
- **Number of divisors: 1**
- **Sum of divisors σ(n): 1**
- **Next prime: 2**
- 검증 출처: Definition: 1 has no prime factors and one divisor

### Mersenne prime 2^61 − 1

- Whole number: 2^61-1
- **Prime factorization: 2305843009213693951**
- **Prime or composite: Prime**
- **Number of divisors: 2**
- 검증 출처: M61 proved prime by Pervushin (1883), OEIS A000668

## 자주 묻는 질문

### 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.

## 출처

- 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](https://arxiv.org/abs/1509.00864)
- [Brent (1980), An improved Monte Carlo factorization algorithm](https://maths-people.anu.edu.au/~brent/pub/pub051.html)