#187 - Semiprimes
A composite is a number containing at least two prime factors. For example, $15=3\times5$; $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<10^8$, have precisely two, not necessarily distinct, prime factors?
Since we are only concerned about numbers with two factors, the larger of the two must not be more than half the limit. We can solve this with a double for loop if we have a prime flag array. The maximum value of the smaller prime can’t exceed the square root of the limit. Once we have this factor, we count all primes that are larger than this prime and add it to a running total. By enforcing the smaller factor, it avoids double counting $2\times 3$ and $3\times 2$ twice. I use primesieve.numpy as pnp so I can easily flag the primes.
# file: "problem187.py"
limit = 10 ** 8
# Only need primes halfway
primes = pnp.primes(limit / 2)
# Take as little space as possible with
# np.uint8
primeFlags = np.zeros(limit // 2, dtype=np.uint8)
primeFlags[primes] = 1
del primes # Get rid of it, we don't need it anymore!
total = 0
i = 0
# The smaller of the two can't exceed the
# square root of the limit...
while i <= limit ** 0.5 + 1:
if primeFlags[i]:
# Count primes up till limit // i to ensure
# the resulting number does not exceed
# the limit.
total += np.sum(primeFlags[i: limit // i + 1])
i += 1
print(total)
Running this short loop, we get
17427258
0.22744560000000003 seconds.
Thus, there are 17427258 composite integers below $10^8$ with exactly two prime factors.
