有9个因数的数

Description

Find the count of numbers less than N having exactly 9 divisors

1<=T<=1000,1<=N<=10^12

思路

两条规则：

1. 有奇数个数因数的数，一定是一个平方数
2. 每个正整数都可以拆解为素数相乘的形式

有9个因数的数N，因数个数是奇数，说明它是一个数x的平方，N = x*x

假设x有4个因数，除了1和本身外，x = p1 * p2, 这里p1和p2都是素数，那么N就可以表示为N = p1*p1*p2*p2

现在来数N的因数：

1

p1

p2

p1*p1

p2*p2

p1*p2

p1*p1*p2

p1*p2*p2

p1*p1*p2*p1

一共是9个因数。

所以我们只要找出有4个因数的x，它的数量就等于有9个因数数字的数量。

怎么找x呢？

1. 首先bound = pow(N, 0.5), 求出小于等于bound的所有素数，两个素数相乘如果小于bound，我们就找到了一个x。

2. 需要注意的是，对于x = p1*p2, 我们假设 p1 != p1， 对于p1 == p2需要额外统计，这种情况的数量等于遍历所有上一步求出的素数，找出满足平方小于bound的素数个数。

具体步骤：

1. 求出小于根号N bound的所有素数放在数列primes中，顺序排列，长度为L
2. 设置两个指针，lo = 0, hi = L-1, 对于每一个hi，检查primes[lo]*primes[hi] 和bound的大小关系
3. 如果小于bound，lo += 1, 继续2
4. 如果大于bound，hi -= 1, 结果加上 lo (因为对于当前primes[hi], 有lo个数字与它相乘小于bound), 继续2
5. 最后lo >= hi 退出2， 结果加上lo(lo+1)//2，因为到这里primes[lo]...primes[0]两两相乘都小于bound。
6. 二叉搜索平方刚好大于bound的素数坐标index，结果加上index。

时间复杂度(O(k))，k是小于根号N的素数个数。

参考实现

n = 10 ** 6 // 2
isPrimes = [False] * 2 + [True] * (n - 1)
for p in range(2, n):
    if not isPrimes[p]: continue
    for i in range(p * 2, n, p):
        isPrimes[i] = False
primes = [i for i in range(n) if isPrimes[i]]

import bisect
def solve(N):
    index = bisect.bisect_left(primes, int(N ** 0.5))
    lo, hi = 0, index
    ans = 0
    while lo < hi:
        while lo < hi and (primes[lo] * primes[hi]) ** 2 <= N:
            lo += 1
        if lo == hi: break
        ans += lo
        hi -= 1
    ans += lo * (lo + 1) // 2
    import math
    ans += bisect.bisect_right(primes, int(math.pow(N, 1 / 8)))
    return ans