Question

有9个因数的数

Answer 1

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

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

两条规则：

有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呢？

具体步骤：

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