In number theory, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime numbers, there are also infinitely many semiprime numbers. Semiprimes are also called biprimes, since they include two primes, or second numbers, by analogy with how "prime" means "first". Alternatively, semiprimes are called almost-prime numbers, specifically the "2-almost-prime" biprime and "3-almost-prime" triprime.
Examples and variations The semiprimes less than 100 are:
Semiprimes that are not square numbers are called discrete, distinct, or squarefree semiprimes:
The semiprimes are the case k = 2 {\displaystyle k=2} of the k {\displaystyle k} -almost primes, numbers with exactly k {\displaystyle k} prime factors. However some sources use "semiprime" to refer to a larger set of numbers, the numbers with at most two prime factors (including unit (1), primes, and semiprimes). These are:
Formula for number of semiprimes Let π 2 ( n ) {\displaystyle \pi _{2}(n)} denote the number of semiprimes less than or equal to n. Then π 2 ( n ) = ∑ k = 1 π ( n ) [ π ( n p k ) − k + 1 ] {\displaystyle \pi _{2}(n)=\sum _{k=1}^{\pi \left({\sqrt {n}}\right)}\left[\pi \left({\frac {n}{p_{k}}}\right)-k+1\right]}
where π ( x ) {\displaystyle \pi (x)} is the prime-counting function and p k {\displaystyle p_{k}} denotes the kth prime. To see this, take p k {\displaystyle p_{k}} to be the smaller prime factor. Then p k ≤ n {\displaystyle p_{k}\leq {\sqrt {n}}} , and the larger factor may be any prime q {\displaystyle q} satisfying p k ≤ q ≤ n / p k {\displaystyle p_{k}\leq q\leq n/p_{k}} . The number of such primes is π ( n / p k ) − π ( p k − 1 ) {\displaystyle \pi (n/p_{k})-\pi (p_{k}-1)} . Since p k {\displaystyle p_{k}} is the kth prime, π ( p k − 1 ) = k − 1 {\displaystyle \pi (p_{k}-1)=k-1} , giving the summand π ( n / p k ) − k + 1 {\displaystyle \pi (n/p_{k})-k+1} .
Properties Semiprime numbers have no composite numbers as factors other than themselves. For example, the number 26 is semiprime and its only factors are 1, 2, 13, and 26, of which only 26 is composite. For a squarefree semiprime n = p q {\displaystyle n=pq} (with p ≠ q {\displaystyle p\neq q} ) the value of Euler's totient function φ ( n ) {\displaystyle \varphi (n)} (the number of positive integers less than or equal to n {\displaystyle n} that are relatively prime to n {\displaystyle n} ) takes the simple form
φ ( n ) = ( p − 1 ) ( q − 1 ) = n − ( p + q ) + 1. {\displaystyle \varphi (n)=(p-1)(q-1)=n-(p+q)+1.}
This calculation is an important part of the application of semiprimes in the RSA cryptosystem. For a square semiprime n = p 2 {\displaystyle n=p^{2}} , the formula is again simple:
φ ( n ) = p ( p − 1 ) = n − p . {\displaystyle \varphi (n)=p(p-1)=n-p.}
… excerpt ends here. Continue reading the full article.
