🧰 ToolPicoAll Tools →
Miller-Rabin based · instant results

Prime Factorization Calculator

Test whether a number is prime instantly, break it into prime factors (2×2×3), list every prime number in a range, find its divisors, see the next/previous primes, and check whether two numbers are coprime — all in one tool, with instant, plain-English results.

4 modes in one tool Up to 18 digits fast Free, no sign-up Updated: Jul 19, 2026
Enter a positive whole number of 1 to 18 digits (up to 10¹⁸). Need more digits? Turn on Extended primality test below.
Lists every prime number in the range using the Sieve of Eratosthenes (up to 2,000,000).
Count only — π(n)Just count the primes in the range (no list), so much larger ranges resolve instantly
Tests whether two positive whole numbers share a common factor (via GCD):
Finds the value of the nth prime number (n up to 200,000).
⚙️ Display settings — divisor list, prime factor tree
Show divisor listList every positive divisor of the number
Show prime factor treeVisualize the factorization step by step
Extended primality testAllow up to ~100 digits via probabilistic BigInt Miller-Rabin (multiple rounds). Results beyond 18 digits are flagged "probabilistic", not certain.
Quick answer A number is prime if it is divisible only by 1 and itself. This tool uses trial division for small numbers and a fast Miller-Rabin-based primality test for large numbers to give an instant answer; if the number isn't prime, it's broken into prime factors like 2×2×3 and its divisors are listed.
168primes between 1 and 1,000
97largest prime under 100
2the only even prime
541the 100th prime number
⚙️ How it works: This tool runs entirely in your browser; no data is sent to a server. Small numbers use trial division, while large numbers use a deterministic Miller-Rabin primality test and Pollard's rho algorithm for factoring — so even 18-digit numbers resolve within seconds. For performance, the range scan is capped at 2,000,000.
🔢 Prime Factorization Calculator — ToolPico ↗

What is a prime number, and how do you test and factor one?

A complete guide — with methods and examples — to the definition of a prime number, primality testing, prime factorization, and coprime numbers.

A prime number is a natural number greater than 1 that is divisible only by 1 and itself. Numbers like 2, 3, 5, 7, 11, 13... are prime; every prime except 2 is odd. Numbers greater than 1 that aren't prime are called composite (e.g. 4, 6, 8, 9); the number 1 is, by definition, neither prime nor composite. By the fundamental theorem of arithmetic, every integer greater than 1 can be written as a product of prime factors in exactly one way — that's exactly what this tool computes.

How can you tell if a number is prime?

Quick answerThe simplest method is trial division: divide the number by every integer from 2 up to its square root; if none of them divide evenly, the number is prime. This method is fast for small numbers but slows down dramatically for large ones (say, 15+ digits). That's why large numbers use fast, probabilistic-deterministic primality tests like Miller-Rabin instead; this tool automatically picks the appropriate method.
  • Trial division: gives an instant result for small numbers (up to a few million).
  • Miller-Rabin test: with the right set of witness values, gives a certain result for numbers up to 18 digits, and is far faster than trial division.
  • Pollard's rho algorithm: finds the factors of large composite numbers with far fewer operations than trial division.

How do you find the prime factorization of a number?

Quick answerStarting from the smallest prime (2), divide the number repeatedly until it no longer divides evenly, then move on to the next prime (3, 5, 7...); this continues until the remaining quotient is 1. The result is written as an exponential product: for example, 360 = 2³ × 3² × 5. This decomposition is unique for every number (aside from ordering).

What are the prime numbers from 1 to 100?

Quick answerThere are 25 prime numbers from 1 to 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. The largest is 97. You can see this list — or scan a larger range — instantly in the "Scan a range" tab above.

What is the Sieve of Eratosthenes?

Quick answerDating back to the 3rd century BC, this method eliminates the multiples of every prime, starting from 2; whatever isn't eliminated is prime. It's simple yet extremely fast even for large ranges; this tool uses exactly this algorithm for its range scan.

What does it mean for two numbers to be coprime?

Quick answerTwo numbers are coprime if they share no common factor other than 1 — that is, their greatest common divisor (GCD) is 1 — without either number needing to be prime itself. For example, 8 and 15 are coprime (GCD = 1) even though neither one is prime. The "Are they coprime?" tab checks this instantly by computing the GCD.

Common prime number examples

Tap any example below and the calculator fills it in automatically and shows the result.

Example numbers, whether they're prime, and their prime factorization
NumberPrime?Prime factorization
97Yes (prime)97
100No2² × 5²
360No2³ × 3² × 5
1,000No2³ × 5³
7,919Yes (1000th prime)7,919
9,973Yes (largest prime under 10,000)9,973
10,000No2⁴ × 5⁴

Popular calculations

Related mini tools: twin prime, perfect number & Mersenne prime

Three more commonly searched number-theory checks — all computed instantly in your browser.

👯Twin prime check
Checks for prime pairs that differ by exactly 2 (e.g. 11 and 13).
💎Perfect number check
Is the sum of a number's divisors (excluding itself) equal to the number? (e.g. 6, 28, 496)
🌀Mersenne prime test
Tests whether a number of the form 2^p − 1 is prime, using the Lucas-Lehmer test.

Reference tables & quick facts

Citable evergreen tables: primes from 1 to 100, divisibility rules, twin primes, and known small Mersenne primes.

The 25 prime numbers from 1 to 100
RangePrimes
1 – 252, 3, 5, 7, 11, 13, 17, 19, 23
26 – 5029, 31, 37, 41, 43, 47
51 – 7553, 59, 61, 67, 71, 73
76 – 10079, 83, 89, 97

25 prime numbers total. Source: Sieve of Eratosthenes (evergreen — a fixed mathematical result).

Divisibility rules that help when factoring into primes
DivisorRule
2If the last digit is even (0,2,4,6,8), the number is divisible by 2.
3If the digit sum is divisible by 3, so is the number.
5If the last digit is 0 or 5, the number is divisible by 5.
7There's no simple shortcut — use direct division.
11If the alternating digit sum (add, subtract, add...) is divisible by 11, so is the number.

These rules quickly suggest which prime to try first; use the calculator above for an exact result.

Known twin prime pairs up to 1,000 (examples)
PairDifference
(3, 5)2
(11, 13)2
(17, 19)2
(29, 31)2
(41, 43)2
(101, 103)2

The twin prime conjecture (that infinitely many twin primes exist) is still an unproven open problem.

Known small Mersenne primes (2^p − 1)
p (exponent)2^p − 1
23
37
531
7127
138,191
17131,071
19524,287

Mersenne primes are directly related to perfect numbers. Test your own value of p in the mini tool above.

Add this calculator to your site (embed code)

Embed the prime factorization calculator on your own website for free. Copy the code below into your HTML — the tool runs in a simplified view and links back to this page as its source.

The embedded tool has a fixed layout; you can adjust the height value to fit your site. No ads or personal data, runs entirely client-side.

Number theory terms glossary

Short definitions of the core terms used around prime numbers.

Prime numberA number greater than 1 that is divisible only by 1 and itself. E.g. 2, 3, 5, 7, 11.
Composite numberA number greater than 1 that isn't prime; it has more than two positive divisors. E.g. 4, 6, 8, 9.
Prime factorA prime number that divides another number. Prime factorization writes these factors in exponential form.
CoprimeTwo numbers with no common divisor other than 1 (GCD = 1).
Twin primeA pair of primes that differ by exactly 2. E.g. (11,13), (17,19).
Sieve of EratosthenesA classic algorithm that finds every prime up to a limit by eliminating multiples.
Perfect numberA number equal to the sum of its own positive divisors, excluding itself. E.g. 6 = 1+2+3.
Mersenne primeA prime of the form 2^p − 1, where p itself must also be prime.
Miller-Rabin testA probabilistic-deterministic primality test far faster than trial division on large numbers.
Divisor-count formulaIf n = p₁^a × p₂^b × ..., the divisor count equals (a+1) × (b+1) × ...
Sum of divisors σ(n)The sum of all positive divisors of a number. For 12, σ = 1+2+3+4+6+12 = 28.
Perfect square / cubeA number is a perfect square if all its prime exponents are even, and a perfect cube if they're all multiples of 3. E.g. 36 = 6², 27 = 3³.

In-depth guides

Detailed answers to the most common questions about prime numbers.

How many primes are there up to 100? The full list and the counting logic

There are exactly 25 prime numbers from 1 to 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. This illustrates how the density of primes gradually thins out among larger numbers: there are 168 primes between 1 and 1,000, and 1,229 between 1 and 10,000.

Enter any start and end value in the "Scan a range" tab above and the tool computes the list and total count instantly using the Sieve of Eratosthenes; you can copy the result or download it as a .txt file.

How can you quickly tell whether a huge number is prime?

Testing a 15-18 digit number by trial division can require checking divisions up to its square root — potentially billions of them — which is impractically slow. Instead, the Miller-Rabin test runs the number through modular exponentiation against a set of specific "witness" values; with the right witness set, it gives a certain result up to a known range (18 digits, in this tool).

If the number is composite, Pollard's rho algorithm finds a factor with far fewer operations than trial division would need on a large composite number; the factors found are then recursively divided down to their own prime factors.

Real-world uses of prime numbers and factorization

Prime numbers underpin modern cryptography: methods like RSA rely on the fact that multiplying two large primes together is easy, but factoring that product back into its prime components is — for sufficiently large numbers — extremely difficult.

On a more everyday level, prime factorization underlies finding the greatest common divisor and least common multiple of numbers, simplifying fractions, and figuring out when periodic events will next coincide.

Frequently asked questions

What is a prime number?
A prime number is a natural number greater than 1 that is divisible only by 1 and itself. Numbers like 2, 3, 5, 7, 11, 13 are prime. Every prime except 2 is odd; 2 is the only even prime. Numbers greater than 1 that aren't prime are called composite; 1 is neither prime nor composite.
How can you tell if a number is prime?
The simplest method is checking whether the number is evenly divisible by any number from 2 up to its square root (trial division); if none divide evenly, it's prime. This slows down for very large numbers, so this tool automatically switches to a fast Miller-Rabin-based test for them.
How do you find the prime factorization of a number?
Starting from the smallest prime (2), divide the number repeatedly until it no longer divides evenly, then move to the next prime (3, 5, 7...); this continues until the remaining quotient is 1. The result is written as an exponential product: for example, 360 = 2³ × 3² × 5. This decomposition is unique for every number (aside from ordering).
What are the prime numbers from 1 to 100?
There are 25 prime numbers from 1 to 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. The smallest is 2, and the largest up to 100 is 97.
What is the Sieve of Eratosthenes?
A 3rd-century-BC algorithm for finding every prime number up to a given limit. Starting from 2, the multiples of each prime are eliminated; whatever numbers are left unmarked are prime. Simple, yet extremely fast for large ranges.
How do you find the divisors of a number?
First break the number into prime factors, then multiply every possible combination of exponents of those factors. For example, 12 = 2² × 3 has the divisors 1, 2, 3, 4, 6, 12 (six divisors). Divisor-count formula: add 1 to each prime's exponent and multiply the results; for 12, (2+1)×(1+1)=6.
What are twin primes?
Pairs of prime numbers that differ by exactly 2: (3,5), (5,7), (11,13), (17,19), (29,31), and so on. Whether infinitely many twin primes exist (the twin prime conjecture) is still an unproven open problem in mathematics.
Why isn't 1 considered a prime number?
By definition, a prime number has exactly two distinct positive divisors (1 and itself); the only divisor of 1 is 1 itself. Also, if 1 were considered prime, the rule that "every number has a unique prime factorization" would break down. That's why 1 is treated as neither prime nor composite.
How do you find the sum of a number's divisors (σ)?
The sum of all positive divisors, σ(n), is found by breaking the number into prime factors and, for each prime, multiplying the values (pexp+1−1)/(p−1). For example, for 12 = 2² × 3, σ = 7 × 4 = 28 (i.e. 1+2+3+4+6+12). This tool shows σ on the result card; numbers whose divisor sum (excluding themselves) equals themselves are called perfect numbers.
What's the smallest multiplier that makes a number a perfect square or cube?
If a number's prime exponents are all even, it's a perfect square; if they're all multiples of 3, it's a perfect cube. To complete it into a perfect square, multiply by the primes with an odd exponent; to complete it into a perfect cube, multiply by whatever brings each exponent up to the next multiple of 3. For example, 12 = 2² × 3 isn't a perfect square; multiplying by 3 gives 36 = 6², a perfect square. The tool shows this smallest multiplier automatically for composite numbers.

Methodology & sources

ToolPico's Prime Factorization Calculator is a free, entirely browser-based number theory tool. Results are not estimates — they are algorithmic and exact. Small numbers use classic trial division; large numbers use a deterministic 12-witness Miller-Rabin primality test (this witness set is chosen so it produces no false positives within the tested range). Large composite numbers are factored using Pollard's rho algorithm. Range scans use the Sieve of Eratosthenes, and the Mersenne prime test uses the Lucas-Lehmer algorithm.

Sources / basis: fundamental theorem of arithmetic · Miller-Rabin primality test · Pollard's rho factorization algorithm · Sieve of Eratosthenes · Lucas-Lehmer test. These concepts are evergreen and don't change over time. Last updated: July 19, 2026.
Explore all ToolPico tools →

🔗 Add this tool to your site

Copy the code below into your own site. The tool is free, always up to date, and runs entirely on your page. No sign-up required.

Preview →
⚡ Built with ToolPico · toolpico.com