Semiprimes

A composite is a number containing at least two prime factors. For example, $15 = 3 \times 5$; $9 = 3 \times 3$; $12 = 2 \times 2 \times 3$.
There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors:
$4, 6, 9, 10, 14, 15, 21, 22, 25, 26$.
How many composite integers, $n \lt 10^8$, have precisely two, not necessarily distinct, prime factors?

This problem is softening your eye to prime number theory and combinatorics.

First, recall the Fundamental Theorem of Arithmetic: any integer greater than 1 is either a prime number, or can be represented as a unique product of prime numbers.

To tackle this, you can do some quick prime counts or use known prime number theorems to get an approximation. For simplicity, we will use a known approximation of the number of primes less than a given number, a result from the prime number theorem. That theorem states that the number of primes less than or equal to n is approximately n / ln(n).

We need to consider two cases.
1) Both prime factors are the same. For this we need the square of a prime to be less than 10^8. We will use the prime counting function which we’ll denote by $\pi(n)$ to find the number of such primes less than $\sqrt{10^8}$ = 10^4. According to pi(10^4), there are approximately around 1229 primes.

2) The prime factors are different. We’ll count this by selecting two different primes and multiplying them together. We need the product of the primes to be less than 10^8, so we’ll consider primes less than $\sqrt{10^8}$. Selecting two from $\pi(10^4)$ primes can be done using combination formula, which gives ${1229\choose2}$.

But, this has couple of over counts. The over counts are when the product of the two primes selected is over 10^8. This means the two primes are both more than $\sqrt{10^8} = 10^4$.

Therefore, we subtract the number of such pairs.

It would seem like we should subtract $\pi(10^4)$ choose 2, but this would eliminate some numbers that are less than 10^8. For example, two primes that are both less than 10^4 but their product is less than 10^8 would be discounted, this shouldn’t happen. It turns out, we only need to subtract out when both primes are greater than $\sqrt[4]{10^8}$.

So, we subtract ${\pi( \sqrt[4]{10^8} )\choose2}$.

So, the final approximation is:

1229 + ${1229\choose2}$ – ${ \pi( \sqrt[4]{10^8} )\choose2}$

This result should be slightly inflated due to the error of the prime counting function but should be reasonably close. It is estimated there are in fact fewer than $\pi(x)$ primes less than $x$ so the number above is likely to be slightly too high.

More Answers: