Product of Two Primes

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.

Examples:
Result
77 is a Semiprime
77 = 7 × 11
Semiprime Type Two Different Primes (p ≠ q)
Coprime Count φ(n) 60
Prime Factors p = 7, q = 11

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:

Two Different Primes (p ≠ q)

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 Squared (p = q)

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 Simulator

Pick two prime numbers below to multiply them together and see all of the new number’s factors:

Resulting Semiprime
77
Two Different Primes (p ≠ q)
All Factors: {1, 7, 11, 77}
Total Factors: 4
Sharing No Factors: φ(77) = 60
02

Looping Shortcut: How Computers Find Hidden Factors

Interactive Lab

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:

Presets:
03

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)
04

4 Step-by-Step Examples

Follow four clear examples of checking semiprimes, counting factors, and spotting hidden prime pairs:

Example 1: The Tricky 91 (7 × 13) Looks Prime!

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.

Example 2: Prime Squares (49 = 7²) Same Prime Twice

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.

Example 3: Splitting 3,233 with Squares Square Shortcut

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.

Example 4: Special Blum Pairs (n = 77) Special Pattern

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.

05

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
06

Where Semiprimes Appear in Space, Math & Security

From deep-space radio messages to unpredictable random bits and quantum computers:

Space Message The 1974 Arecibo Message (1,679 = 23 × 73)

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.

Proven Lock Security The Rabin Security 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.

Random Number Design The Blum-Blum-Shub Bit Generator

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 Milestones Testing Early Quantum Computers

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.