c - 找出具有素数因数的数字的个数

Question

问题是求一个数的约数

前-

for 10 

ans=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;

}

有人可以帮我优化它吗？

我也搜索过，但没有成功。

所以请大家帮忙。

Answer 1

你可以尝试用数学方法计算这个(我不确定这会更快/更容易)。基本上，给定一个数的素因数分解，您应该能够毫不费力地计算除数的数量。

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

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

那么除数的个数应该是

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

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

现在考虑一下上面的陈述:质因数分解的幂(加 1)的乘积中的除数的数量。因此，如果您只关心结果是否为素数，那么您应该只考虑素数或素数的幂。在此范围内，您只需要考虑 a1 + 1 是素数的幂。

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