-9

问题是找到一个数的除数

前任-

for 10

答案=4

因为 1,2,5,10 是除数

即它们是因素

约束是 num<=10^6

我已经实现了相同的代码，但得到了 TLE！

这是我的代码

int isprime[MAX];

void seive()
{

    int i,
    j;

    isprime[0] = isprime[1] = 1;

    for (i = 4; i < MAX; i += 2) 
        isprime[i] = 1;

    for (i = 3; i * i < MAX; i += 2) {
        if (!isprime[i]) {
            for (j = i * i; j < MAX; j += 2 * i) 
                isprime[j] = 1;

        }

    }

}
int main()
{

    seive();

    int t;

    long long num;

    scanf("%d", & t);

    while (t--) {

        scanf("%lld", & num);



            cnt = 0;

            for (j = 1; j * j <= num; j++) {
                if (num % j == 0) {
                    cnt++;

                    if (num / j != j) 
                        cnt++;

                }





        printf("%lld\n", cnt);

    }

    return 0;

}

有人可以帮我优化它吗？

我也搜索过它，但没有得到任何成功。

所以请帮助大家。

4

2 回答 2

4

您可以尝试以数学方式计算（我不确定这会更快/更容易）。基本上，给定一个数字的素数分解，您应该能够轻松计算除数的数量。

如果你有一个输入x分解成类似

x = p1^a1 * p2^a2 * ... pn^an

那么除数的数量应该是

prod(ai + 1) for i in 1 to n

然后，我会寻找最小的素数 < sqrt(x)，然后将其分开，直到只剩下一个素数。筛子可能仍然有用，我不知道你会得到什么样的输入。

现在考虑上述陈述的内容：素数分解（加 1）的幂的乘积中的除数。因此，如果您只关心结果是否为素数，那么您应该只考虑素数或素数的幂。在此范围内，您只需要考虑使 a1 + 1 为素数的幂。

这应该会大大减少您的搜索空间。

于 2013-11-01T18:29:09.453 回答
3

如果一个数的素数分解是：

x = p1^e1 * p2^e2 * ... * pk^ek

那么除数的数量是：

(e1 + 1)*(e2 + 1)* ... *(ek + 1)

要使其成为素数，您需要全部ei为 0，除了一个，它必须是素数 - 1。

这仅适用于素数和素数的幂。所以你需要找出素数有多少次幂[l, r]。例如，2^6具有(6 + 1) = 7素因数。

现在您只需要足够快地筛选出足够多的素数。您只需要筛选那些 in [l, r]，因此间隔大小为 max 10^6。

要直接在此区间内筛选，请直接从 中删除 2 的倍数，[l, r]其余部分相同。您可以筛选素数，10^6并在以后使用它们进行间隔筛选。

您也可以在筛分时进行必要的计数。

于 2013-11-01T18:21:32.433 回答