小于30的合数中，有十个合数恰有两个（不一定互异）质因数：$4, 6, 9, 10, 14, 15, 21, 22, 25, 26$。

有多少个小于$10^8$的合数恰有两个（不一定互异）质因数？

本题难度:

不妨设所考虑的数是$n=pq$，其中p,q都是质数且$p\le q$。

若$p=2$，则显然q可以取2到五千万之间的素数。

若$p=3$，则q可以取3到$10^8/3$之间的素数。

。。。

以此类推，因此只需生成五千万以内的素数表，再二分查找$n/p$，最后汇总即得结果$17427258$。

import bisect
target=50000000
d=[0]*target
n=2
while n < target:
    for i in range(n*n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1
p=[k for k in range(2,target) if d[k]==0]

z=10**8
r=0
for i,j in enumerate(p):
    k=z/j
    if k>j:
        r+=bisect.bisect(p,k)-i
    else:
        break

print r