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
360 = 2³ × 3² × 5, so it is composite with 24 divisors adding up to 1170. The nearest primes are 359 and 367.
| Divisor | Paired divisor n ÷ d |
|---|---|
| 1 | 360 |
| 2 | 180 |
| 3 | 120 |
| 4 | 90 |
| 5 | 72 |
| 6 | 60 |
| 8 | 45 |
| 9 | 40 |
| 10 | 36 |
| 12 | 30 |
| 15 | 24 |
| 18 | 20 |
Each prime is divided out as many times as it goes before moving on.
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⁻²⁰.
검증 출처: Python 3.8 trial division and divisor enumeration (scratchpad forkA/verify.py)
검증 출처: Project Euler #3 (largest prime factor 6857); product and primality checked in Python 3.8
검증 출처: F. N. Cole, 1903 (Bull. AMS 10:134); product and primality of both factors checked by Python trial division
검증 출처: Table of primes (OEIS A000040): 89, 97, 101
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.
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.
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.
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.
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.
이 계산기에는 독립적인 출처에서 답을 얻은 계산 예제가 6개 있습니다. 테스트 모음에서 실행되며 여기에서도 실행할 수 있습니다.
Greatest common divisor (GCD, GCF or HCF) and least common multiple (LCM) of two or more whole numbers, with Euclid's algorithm step by step.
Calculate a mod n under the floored, truncated and Euclidean conventions, modular powers a^b mod m of large numbers, and modular inverses, with steps.
Factor calculator: every factor and factor pair of a whole number up to 10¹⁸, its prime factorization, divisor count and sum, and perfect or abundant.