Semiprime
In number theory, a semiprime is a natural number that is the product of exactly two prime numbers, which may be equal or distinct.[1] Examples include 4 = 2 × 2, 6 = 2 × 3, 9 = 3 × 3, 10 = 2 × 5, 14 = 2 × 7, 15 = 3 × 5, 21 = 3 × 7, and 22 = 2 × 11.[1] Semiprimes form a significant subclass of composite numbers, bridging primes and more highly composite forms in the study of integer factorization and distribution.[1] The counting function π₂(x), which tallies the number of semiprimes less than or equal to x, has an asymptotic approximation of x (log log x) / log x, indicating their relative abundance compared to primes but sparsity relative to all integers.[2] This density arises from the multiplicative structure, where semiprimes include both squares of primes (such as 4, 9, 25) and square-free semiprimes (products of distinct primes, such as 6, 10, 15).[1] Beyond pure mathematics, semiprimes are foundational to computational number theory and cryptography, as factoring a large semiprime into its constituent primes is computationally intractable for sufficiently large instances, a property exploited in algorithms like RSA.[3] In the RSA cryptosystem, the public key modulus is typically a semiprime formed by multiplying two large distinct primes, ensuring security relies on the presumed hardness of this factorization problem.[4] Notable challenges, such as the factorization of RSA-129 (a 129-digit semiprime) in 1994, underscore both historical progress and ongoing research into semiprime properties.[1]Definition and Fundamentals
Definition
A semiprime is a natural number that is the product of exactly two prime numbers, not necessarily distinct.[1] For instance, $4 = 2 \times 2 and $6 = 2 \times 3 are semiprimes.[1] Formally, a semiprime n can be expressed as n = p \times q, where p and q are prime numbers with p \leq q.[5] Semiprimes differ from prime numbers, which have only one prime factor (themselves), and from higher prime powers such as $8 = 2^3, which involve more than two identical prime factors.[1] The number 1 is excluded, as it is not the product of any primes.[5] The term "semiprime" derives from "semi-" combined with "prime" and is used in number theory to describe such numbers with exactly two prime factors, counting multiplicity.[6]Types
Semiprimes can be classified based on whether their prime factors are identical or distinct, as well as by their parity and square-freeness. A square semiprime is the square of a prime number, denoted as n = p^2 where p is prime; examples include 4 ($2^2), 9 ($3^2), and 25 ($5^2).[1] These form the sequence of prime squares, cataloged in OEIS A001248. In contrast, a non-square semiprime, also known as a distinct or discrete semiprime, is the product of two distinct primes, n = p \times q with p \neq q and both prime. Examples include 6 ($2 \times 3), 10 ($2 \times 5), and 15 ($3 \times 5).[1] These are precisely the square-free semiprimes, meaning they have no squared prime factors, and they constitute the sequence in OEIS A006881.[7] Semiprimes can further be categorized by parity. An even semiprime is divisible by 2, which implies one of its prime factors must be 2, yielding forms like $2 \times p where p is an odd prime (or $2^2 = 4 for the square case); representative examples are 6, 10, and 14.[1][8] Conversely, an odd semiprime has both prime factors odd, resulting in products like p \times q with p and q odd primes (or p^2 for odd p); examples include 15, 21 ($3 \times 7), and 25.[1]Examples
Small Semiprimes
The smallest semiprimes are the natural numbers greater than 1 that have exactly two prime factors, counted with multiplicity, denoted by the condition \Omega(n) = 2, where \Omega(n) is the total number of prime factors of n (with repetition).[9] This includes both squares of primes (p^2) and products of two distinct primes (p \times q). The sequence of semiprimes begins with 4, 6, 9, 10, and continues, with all terms up to 100 listed below along with their factorizations.[5][1] Among these, even semiprimes except for 4 are all of the form $2 \times p, where p is an odd prime, since any even number greater than 2 must include 2 as a factor and, to remain a semiprime, the cofactor must be prime.[1] The density of semiprimes appears to increase initially in this range, with 34 such numbers up to 100, illustrating their relative frequency among small composites.[5]| Semiprime | Factorization |
|---|---|
| 4 | $2^2 |
| 6 | $2 \times 3 |
| 9 | $3^2 |
| 10 | $2 \times 5 |
| 14 | $2 \times 7 |
| 15 | $3 \times 5 |
| 21 | $3 \times 7 |
| 22 | $2 \times 11 |
| 25 | $5^2 |
| 26 | $2 \times 13 |
| 33 | $3 \times 11 |
| 34 | $2 \times 17 |
| 35 | $5 \times 7 |
| 38 | $2 \times 19 |
| 39 | $3 \times 13 |
| 46 | $2 \times 23 |
| 49 | $7^2 |
| 51 | $3 \times 17 |
| 55 | $5 \times 11 |
| 57 | $3 \times 19 |
| 58 | $2 \times 29 |
| 62 | $2 \times 31 |
| 65 | $5 \times 13 |
| 69 | $3 \times 23 |
| 74 | $2 \times 37 |
| 77 | $7 \times 11 |
| 82 | $2 \times 41 |
| 85 | $5 \times 17 |
| 86 | $2 \times 43 |
| 87 | $3 \times 29 |
| 91 | $7 \times 13 |
| 93 | $3 \times 31 |
| 94 | $2 \times 47 |
| 95 | $5 \times 19 |
Notable Examples
1 is excluded from the class of semiprimes, as it is not the product of two prime numbers; semiprimes require exactly two prime factors, counting multiplicity, and 1 has none.[1] The smallest odd semiprime with distinct prime factors is 15 = 3 × 5, marking an early historical example in the study of composite numbers beyond even semiprimes like 4 = 2 × 2 or 6 = 2 × 3.[1] In number theory puzzles and primality testing, semiprimes like 91 = 7 × 13 serve as notable examples of Fermat pseudoprimes; specifically, 91 is a pseudoprime to base 3, satisfying 3^{90} ≡ 1 (mod 91) despite being composite, which highlights their role in deceiving certain primality tests.[10] In contrast, the first Carmichael number, 561 = 3 × 11 × 17, is a product of three primes and passes Fermat's test for all bases coprime to it, but semiprimes like 91 illustrate similar deceptive behavior for specific bases. Semiprimes appear infrequently as Mersenne numbers M_n = 2^n - 1, but notable cases include M_{11} = 2047 = 23 \times 89, the smallest Mersenne number that is a strong pseudoprime to base 2, and M_4 = 15 = 3 \times 5, the smallest such semiprime overall. Other indices yielding Mersenne semiprimes include 9 ($511 = 7 \times 73), 23 ($8388607 = 47 \times 178481), and 37, underscoring their rarity and utility in studying composite Mersenne forms.[11] Among large-scale records, the RSA-250 semiprime, a 250-decimal-digit number (~829 bits) from the RSA Factoring Challenge, represents a milestone as the largest such semiprime fully factored to date (as of 2025), achieved in February 2020 using the general number field sieve after approximately 2700 core-years of computation; its prime factors are two 125-digit primes, demonstrating the practical limits of classical factoring algorithms.[12]Properties
Arithmetic Properties
A semiprime n = p q, where p and q are primes (not necessarily distinct), exhibits specific divisibility properties determined by its prime factorization. If n is square-free, meaning p \neq q, then the positive divisors of n are exactly $1, p, q, and pq, yielding precisely four divisors.[13] In contrast, if n is the square of a prime, so n = p^2, the divisors are $1, p, and p^2, resulting in exactly three divisors.[13] These counts distinguish semiprimes from primes (two divisors) and numbers with more prime factors (more than four divisors for square-free cases).[14] The sum of divisors function \sigma(n), which sums all positive divisors of n, takes a straightforward form for semiprimes due to the multiplicativity of \sigma. For a square-free semiprime n = p q with distinct primes p and q, \sigma(n) = (1 + p)(1 + q).[15] For a prime square n = p^2, \sigma(n) = 1 + p + p^2.[15] These expressions arise directly from the geometric series sum for each prime power factor.[14] Euler's totient function \phi(n), counting the integers up to n that are coprime to n, is also multiplicative and simplifies for semiprimes. For n = p q with p \neq q, \phi(n) = (p - 1)(q - 1).[16] When n = p^2, \phi(n) = p(p - 1).[16] These formulas reflect the exclusion of multiples of p and q from the count of coprimes. The greatest common divisor (GCD) and least common multiple (LCM) of a semiprime with another integer follow from their prime factorizations. For two square-free semiprimes n = p q and m = r s with all distinct primes, \gcd(n, m) = 1 and \operatorname{lcm}(n, m) = p q r s. If they share one prime, say p = r but q \neq s, then \gcd(n, m) = p and \operatorname{lcm}(n, m) = p q s. In general, \gcd(n, m) is the product of the shared prime factors raised to the minimum exponent, while \operatorname{lcm}(n, m) uses the maximum exponents. Semiprimes are not closed under multiplication: the product of two semiprimes is generally not a semiprime. For instance, the product of two square-free semiprimes n = p q and m = r s (all distinct primes) equals p q r s, which has four distinct prime factors and thus more than two.[1] Even if some primes coincide, the result typically has more than two prime factors counting multiplicity, unless specifically arranged to reduce to exactly two.[1]Analytic Properties
Semiprimes are asymptotically equidistributed between the odd residue classes modulo 4, with the number ≤ x congruent to 1 mod 4 and to 3 mod 4 each ∼ (1/2) x (log log x) / log x. While temporary biases may occur due to the distribution of primes, the leading asymptotics show no disparity. More generally, semiprimes ≤ x are asymptotically equidistributed among the residue classes a mod q with gcd(a, q) = 1, each with asymptotic ∼ [1/φ(q)] x (log log x) / log x.[17] A direct link exists between Sophie Germain primes and semiprimes: if p is a Sophie Germain prime (i.e., both p and $2p + 1 are prime), then the product p(2p + 1) is a semiprime.[18] This construction yields specific semiprimes where the factors are related by the doubling relation, and such products appear in studies of prime chains and Cunningham chains of length 2.[18] Semiprimes can behave like primes under certain probabilistic tests, notably as Fermat pseudoprimes. A composite number n is a Fermat pseudoprime to base b if b^{n-1} \equiv 1 \pmod{n}, despite n not being prime; the smallest such semiprime is 341 = 11 × 31, which satisfies $2^{340} \equiv 1 \pmod{341}.[19] These instances arise when the factors of the semiprime share compatible orders in the multiplicative group, fooling the Fermat test and illustrating analytic similarities to primes in modular exponentiation.[19] The density of semiprimes in arithmetic progressions follows from extensions of the prime number theorem, with positive asymptotic density in progressions a \pmod{q} where \gcd(a, q) = 1. This mirrors the equidistribution of primes but scaled by the semiprime counting function \pi_2(x) \sim \frac{x \log \log x}{\log x}, first established by Landau.[17] Landau's foundational work on this asymptotic underpins related unsolved problems, such as the infinitude of primes in certain forms that influence semiprime distributions.[17]Enumeration
Counting Formulas
The number of semiprimes less than or equal to a given positive real number x, denoted \pi_2(x), can be exactly determined using the prime-counting function \pi(y), which gives the number of primes less than or equal to y. The formula is \pi_2(x) = \sum_{\substack{p \prime \\ p \le \sqrt{x}}} \left( \pi\left( \frac{x}{p} \right) - \pi(p-1) \right), where the sum is taken over all prime numbers p \le \sqrt{x}.[1] This expression arises from counting the products p q \le x where p and q are primes with p \le q. For each fixed prime p \le \sqrt{x}, the number of suitable q \ge p is the number of primes in the interval [p, x/p], which is \pi(x/p) - \pi(p-1). The formula naturally includes the prime squares p^2 \le x, as each such square is counted when q = p in the term for that p; the total number of such squares is \pi(\sqrt{x}).[1] The enumeration of semiprimes, including this exact counting formula, was first systematically studied by Edmund Landau in his 1909 monograph Handbuch der Lehre von der Verteilung der Primzahlen. For practical computation of \pi_2(x), especially for moderate x, sieve methods are effective. First, generate all primes up to x using the Sieve of Eratosthenes. Then, to count semiprimes, initialize an array of size x+1 to zero and, for each prime p, iterate over primes q \ge p such that p q \le x, incrementing the array at position p q. The number of non-zero entries in the array up to x (or specifically those marked exactly once, ensuring no overcounting from multiple representations) gives \pi_2(x). Alternatively, a modified sieve can track the number of prime factors for each number up to x, counting those with exactly two (counting multiplicity for squares). These methods have time complexity O(x \log \log x). Recurrence relations for \pi_2(x) are less common, but the formula itself allows recursive computation if \pi(y) values are precomputed or approximated for smaller y, leveraging known recurrences or tabulations for the prime-counting function. The following table provides computed values of \pi_2(x) for small x using the exact formula:| x | \pi_2(x) |
|---|---|
| 10 | 4 |
| 100 | 34 |
| 1000 | 299 |
| $10^4 | 2625 |