Semiprime Calculator
Check whether any whole number is built from exactly two prime numbers (n = p × q), view all of its factors, and see how it works in real life.
1. Two Types of Semiprimes: Different Primes vs. Prime Squares
A semiprime is any whole number made by multiplying exactly two prime numbers together (either two different primes, or one prime multiplied by itself). Every semiprime fits into one of two simple groups:
Made from two separate primes. Examples: 6 = 2 × 3, 15 = 3 × 5, 77 = 7 × 11.
- Total Factors: Exactly 4 (1, p, q, and n)
- Numbers sharing no factors: (p − 1) × (q − 1)
- Square factor check: Contains no repeating square
One prime number multiplied by itself. Examples: 4 = 2², 9 = 3², 49 = 7².
- Total Factors: Exactly 3 (1, p, and p²)
- Numbers sharing no factors: p × (p − 1)
- Square factor check: Is a perfect square itself
Build Your Own Semiprime
Live SimulatorPick two prime numbers below to multiply them together and see all of the new number’s factors:
Looping Shortcut: How Computers Find Hidden Factors
Checking every divisor one by one is slow on big numbers. Instead, mathematician John Pollard invented a clever race-track shortcut (known as Pollard’s rho method): two markers step forward at different speeds using the remainder rule (x² + 1) ÷ n until their paths sync up and reveal a secret factor! Try any number below to watch:
20 Famous Semiprimes
Explore well-known two-prime numbers—from tricky fake primes to quantum tests and deep-space radio messages:
| Number n | Factors (p × q) | Type | Coprime φ(n) | Divisors | Why It’s Notable | Try |
|---|---|---|---|---|---|---|
| 4 | 2 × 2 | Prime Squared (p²) | 2 | 3 | Smallest squared prime (2 × 2) | |
| 6 | 2 × 3 | Two Primes (p ≠ q) | 2 | 4 | Smallest product of two different primes | |
| 9 | 3 × 3 | Prime Squared (p²) | 6 | 3 | Smallest odd squared prime (3 × 3) | |
| 10 | 2 × 5 | Two Primes (p ≠ q) | 4 | 4 | Our everyday base-10 number (2 × 5) | |
| 14 | 2 × 7 | Two Primes (p ≠ q) | 6 | 4 | Even two-prime product | |
| 15 | 3 × 5 | Two Primes (p ≠ q) | 8 | 4 | Smallest odd two-prime product | |
| 21 | 3 × 7 | Two Primes (p ≠ q) | 12 | 4 | Split on an early quantum computer (2012) | |
| 25 | 5 × 5 | Prime Squared (p²) | 20 | 3 | Square of prime 5 (5²) | |
| 33 | 3 × 11 | Two Primes (Blum) | 20 | 4 | Blum pair (both primes leave rem 3 ÷ 4) | |
| 35 | 5 × 7 | Two Primes (p ≠ q) | 24 | 4 | Split on an early quantum computer (2019) | |
| 49 | 7 × 7 | Prime Squared (p²) | 42 | 3 | Square of prime 7 (7²) | |
| 77 | 7 × 11 | Two Primes (Blum) | 60 | 4 | Blum pair used in randomizers | |
| 91 | 7 × 13 | Two Primes (p ≠ q) | 72 | 4 | Tricky composite (looks prime at a glance!) | |
| 143 | 11 × 13 | Two Primes (p ≠ q) | 120 | 4 | Product of twin primes 11 and 13 | |
| 221 | 13 × 17 | Two Primes (p ≠ q) | 192 | 4 | Difference of squares: 15² − 2² | |
| 3,233 | 53 × 61 | Two Primes (p ≠ q) | 3,120 | 4 | Classic classroom RSA lock number | |
| 10,403 | 101 × 103 | Two Primes (p ≠ q) | 10,200 | 4 | Easy to crack: 102² − 1² | |
| 1,679 | 23 × 73 | Two Primes (p ≠ q) | 1,584 | 4 | 1974 Arecibo radio message into space | |
| 2,047 | 23 × 89 | Two Primes (p ≠ q) | 1,936 | 4 | First non-prime 2^p − 1 number (2¹¹ − 1) | |
| 100,140,063 | 10007 × 10009 | Two Primes (p ≠ q) | 100,120,048 | 4 | Close twin-prime product (cracked in 1 try) |
4 Step-by-Step Examples
Follow four clear examples of checking semiprimes, counting factors, and spotting hidden prime pairs:
At first glance, 91 looks prime because it is odd, its digits add up to 10 (not divisible by 3), and it does not end in 5. But when testing prime numbers up to its square root (which is about 9.5), 7 divides into 91 evenly: 91 ÷ 7 = 13! Because both 7 and 13 are prime, 91 is a semiprime number made of two different primes.
When a prime is multiplied by itself (like 7 × 7 = 49), it creates a square semiprime. Any square of a prime number has exactly 3 factors: 1, the prime itself, and the square. For 49, its only factors are 1, 7, and 49.
To factor 3,233, we test squares near its square root (about 56.8). Testing 57: 57² = 3,249. Subtracting 3,233 leaves 16, which is 4². That gives the two factors immediately: 57 − 4 = 53 and 57 + 4 = 61. This method works very quickly whenever two primes are close together.
A Blum number is a semiprime where both primes leave a remainder of 3 when divided by 4 (like 7 and 11, because 7 = 4 + 3 and 11 = 8 + 3). These special numbers have neat square-root properties that programmers use in digital security.
How Fast Computers Split Semiprimes
Splitting a big number built from just two large primes (n = p × q) is much harder than factoring everyday numbers that divide cleanly by 2, 3, or 5—because there are no small factors to peel off first:
| Method | Approach | Speed | Memory Needed | Best Used For |
|---|---|---|---|---|
| Divide One by One | Exact search | Slow on large numbers | Tiny | Everyday numbers under 100 trillion |
| Fermat’s Square Method | Exact search | Matches gap |p − q| | Tiny | Cracking primes chosen too close together |
| Pollard’s Looping Method | Cycle shortcut | Much faster | Tiny | Medium numbers up to ~18 digits |
| Quadratic Sieve | Pattern sieve | Moderate growth | Large table | Numbers up to 100 digits |
| Number Field Sieve | Advanced sieve | Best regular method | Supercomputer RAM | Giant numbers above 100 digits |
| Shor’s Quantum Method | Quantum math | Fast (future) | Large quantum chip | Future fault-tolerant quantum computers |
Where Semiprimes Appear in Space, Math & Security
From deep-space radio messages to unpredictable random bits and quantum computers:
When astronomers Carl Sagan and Frank Drake beamed humanity’s first radio message toward distant stars from the Arecibo telescope, they sent exactly 1,679 signals. Because 1,679 is a semiprime, it only forms one natural picture grid: 23 across by 73 down (or 73 by 23)—drawing DNA, a human stick figure, and the Solar System.
Even in RSA, scientists strongly suspect—but haven’t strictly proven—whether decoding a message requires factoring n. In 1979, Michael O. Rabin designed a squaring lock where decoding a scrambled number is strictly proven to be just as hard as splitting n = p × q back into its two primes.
By repeatedly squaring a number and keeping the remainder divided by a special Blum semiprime M, computers can pull out an endless stream of unpredictable 0s and 1s. Predicting the next random bit is impossible unless someone can factor M.
Quantum hardware teams often test their progress by factoring small semiprimes: researchers split 15 = 3 × 5 in 2001, 21 = 3 × 7 in 2012, and 35 = 5 × 7 in 2019. Cracking full 600-digit internet keys would still require thousands of error-free quantum bits that do not exist yet.
Related Prime & Factoring Calculators
Frequently Asked Questions
What is a semiprime number in mathematics?
A semiprime number is a whole number made by multiplying exactly two prime numbers together: n = p × q. The two primes can be different (like 15 = 3 × 5) or the same (like 49 = 7 × 7).
Is 49 considered a semiprime number?
Yes, 49 is a semiprime number because it is made by multiplying exactly two primes together: 7 × 7. The four prime squares under 100 are 4 (2²), 9 (3²), 25 (5²), and 49 (7²).
How many factors does a semiprime have?
If the two primes are different (like 15 = 3 × 5), the number has exactly 4 factors: 1, the two primes, and the number itself (1, 3, 5, 15). If the prime is multiplied by itself (like 49 = 7²), it has exactly 3 factors (1, 7, 49).
Why are semiprimes important for internet security?
Internet security systems like RSA create their secret locks by multiplying two huge prime numbers together to form a giant semiprime. While multiplying two numbers takes a split second, reversing the process to find the original primes can take millions of years for computers.
What is a Blum semiprime?
A Blum number is a semiprime where both prime numbers leave a remainder of 3 when divided by 4 (such as 33 = 3 × 11 or 77 = 7 × 11). They have helpful symmetry used in secure random number generation.
Why was a semiprime chosen for the 1974 Arecibo radio message?
The 1974 Arecibo message beamed into space contained exactly 1,679 binary pulses. Because 1,679 is a semiprime (23 × 73), it can only be arranged into a neat rectangle in two ways: 23 rows by 73 columns, or 73 rows by 23 columns. This guaranteed that any intelligent recipients could easily assemble the pixels into a picture.