187. 半素数(Semiprimes)

合数是指包含至少两个质因数的整数,例如\(15=3\times5,9=3\times3,12=2\times2\times3\)。在小于30的合数中,有十个合数包含恰好两个不一定不同的质因数:\(4, 6, 9, 10, 14, 15, 21, 22, 25, 26\)。求在\(n<10^8\)范围内有多少个合数包含恰好两个不一定不同的质因数?

分析:我们首先来看一下题目中给出的例子,如果要求三十以内的半素数应该怎么做。我们知道最小的素数是二,所以这些半素数的质因数最大不能超过\(30/2=15\),也就是说只要找到15以内的素数就可以了,这包括2、3、5、7、11、13总共六个素数。我们从2开始看,显然2可以和包括自身在内的素数相乘形成半素数,所有总共有六个;再来看3,为了避免重复计数,我们只看3和比它大的素数的乘积,因为\(30/3=10\),所以和3相乘的素数不能大于10,所以只有3,5,7满足条件,共有三个;再来看5,同理\(30/5=6\),只看不小于五且不大于6的素数,因此只有五符合条件,共有一个;所以三十以内的半素数共有\(6+3+1=10\)个。

对于一般的情况,设\(\pi(x)\)表示小于等于\(x\)的数中的素数个数,如\(\pi(10)=4\),则对于小于\(n\)范围内半素数,假设其两个质因数中较小者为\(p\),则其另外一个质因数不能超过\(\lfloor \left( n-1 \right) /p \rfloor\),这个范围内的素数个数有\(\pi \left( \lfloor \left( n-1 \right) /p \rfloor \right)\)个;为避免重复计数,需要从这个数中减去小于\(p\)的素数个数,假设\(p_i\)是第\(i\)个素数,即\(p_1=2,p_2=3,p_3=5\)等等,则小于\(p_i\)的素数有\((i-1)\)个。故在小于\(n\)的范围内且最小质因数为\(p_i\)半素数个数\(c(p_i)=\pi \left( \lfloor \left( n-1 \right) /p_i \rfloor \right) -i+1\)

显然,小于\(n\)范围内的半素数的最大质因数不能超过\(\sqrt{n}\),也即\(p_i\le\sqrt{n}\),故有\(i\le\pi(\sqrt{n})\),则小于\(n\)范围内的半素数个数共有:

$$ {\displaystyle \pi _{2}(n)=\sum _{i=1}^{\pi ({\sqrt {n}})}[\pi ((n-1)/p_{i})-i+1]} $$

使用这个公式,我们可以很容易的计算出特定范围内的半素数的个数,代码如下:

# time cost = 1.51 s ± 5.57 ms

from sympy import primerange,primepi

def main(N=10**8):
    c =  0
    u = int(N**0.5)
    primes = primerange(1,u+1)
    for n,p in enumerate(primes):
        c += primepi((N-1)//p)-n
    return c