然而，它简化为
查找所有 SEMPIPRIMES (2个不同质因数的乘积，如6(2*3)，范围从L到R)
将会有多个L和R的查询
由于N很大，我们不能预先计算半数。
但是，我们可以存储原始值，因为它们只到了 根据问题，10^6
现在，假设我有所有的质数，由 筛网
我需要所有可能的L到R之间的乘积对。
或问题简化为给定一个排序阵列。找出所有可能的搭配，包括L和R之间的产品。
我把这部分代码写进了编辑部。
for(int i=0; i<cnt and ar[i]<=r; i++)
{
int lower = L/ar[i];
if(L%ar[i]>0)
lower++;
lower = max(lower, ar[i]+1);
int upper = R/ar[i];
if(upper<lower)
continue;
ans += upper_bound(ar.begin(),ar.end(),upper)-
lower_bound(ar.begin(),ar.end(),lower);
}
这里有一个方法，这个方法可能不快，但似乎很合理。
参考一下。https:/en.wikipedia.orgwikiPime -counting_function.
半质数的生成过程已经有了。每个半质数都是 2 个不同质因数的乘积。
所以，我们可以保留一个数组，这个数组将存储所有的半质数，因为在这个范围内最多只有10^5个半质数，我们可以对这个数组进行排序。对于每次查询，我们只需要在数组上进行二进制搜索，就可以找到这个范围内的元素数。
我们可以稍微修改一下Eratosthenes的筛子来生成半数。
我们的想法是，我们将保留一个 countDivision 数组，它将存储范围内每个整数的除数。我们只考虑一个整数的半质数是 countDivision 该整数的索引值为2（2个除数）。
def createSemiPrimeSieve(n):
v = [0 for i in range(n + 1)]
# This array will initially store the indexes
# After performing below operations if any
# element of array becomes 1 this means
# that the given index is a semi-prime number
# Storing indices in each element of vector
for i in range(1, n + 1):
v[i] = i
countDivision = [0 for i in range(n + 1)]
for i in range(n + 1):
countDivision[i] = 2
# This array will initially be initialized by 2 and
# will just count the divisions of a number
# As a semiprime number has only 2 prime factors
# which means after dividing by the 2 prime numbers
# if the index countDivision[x] = 0 and v[x] = 1
# this means that x is a semiprime number
# If number a is prime then its
# countDivision[a] = 2 and v[a] = a
for i in range(2, n + 1, 1):
# If v[i] != i this means that it is
# not a prime number as it contains
# a divisor which has already divided it
# same reason if countDivision[i] != 2
if (v[i] == i and countDivision[i] == 2):
# j goes for each factor of i
for j in range(2 * i, n + 1, i):
if (countDivision[j] > 0):
# Dividing the number by i
# and storing the dividend
v[j] = int(v[j] / i)
# Decreasing the countDivision
countDivision[j] -= 1
# A new vector to store all Semi Primes
res = []
for i in range(2, n + 1, 1):
# If a number becomes one and
# its countDivision becomes 0
# it means the number has
# two prime divisors
if (v[i] == 1 and countDivision[i] == 0):
res.append(i)
return res
信用。https:/www.geeksforgeeks.orgprint-all-semi-prime-numbers-less-than-or-equal-to-n
但是，生成的复杂度与筛子相同，即 O(nloglogn). 如果(R-L)是<10^5，这个方法就可以通过。但由于（R-L）可以大到10^8，所以不可行。
另一种方法是 计数 而不是生成。
让我们来研究一个例子。
2 10
现在，让我们假设，我们知道所有的质数，直到10^6（为 p 和 q 不能超过10^6）。)
primes = [2, 3, 5, 7, 11, ...]
10^6以下的质数小于10^5（所以我们可以把它们存储在一个数组中），时间复杂度也是可以控制的。
现在，我们可以扫描我们的 primes 数组来计算每个质数的贡献，以生成范围(L，R)内的半质数。
首先，我们从2开始，借助2来生成多少个半质数。
让我们看看primes = [2, 3, 5, 7, 11, ..]
我们不能选择2，因为2和2不一样（p、q一定不一样）。但是，3在，因为2*3 <=10，所以5也在，2*5 2*5 <=10。
这个怎么算呢？
我们将下界取为2/2 (L//primes[i]) 但我们必须确保，我们不会再考虑当前的质数，因为（p和q一定是不同的），所以我们取最大的 L//primes[i] 和 primes[i]+1.
对于2，我们的起始数是3（因为2+1=3，我们不能从1或2开始，因为如果考虑2，那么我们会计算出2*2=4这样的情况，是不成立的）。我们的末尾数是10/2=5，在3、5的范围内，质数中有多少个数。是2，通过简单的二进制搜索就可以找到。
其余的就简单了，我们要二进制搜索范围内有多少个质数。(max(L//primes[i], primes[i]+1), R//primes[i]).
这具有复杂度预处理时间复杂度为O(10^6*log(10^6))+O(10^6*log(10^6))和O(log(10^6))每次查询。