整数的质因子分解 为什么time limit exceed

图片说明

 #include <stdio.h>
#include <math.h>
int isPrime(int k)
{
    int i;
    for (i = 2; i <= sqrt(k); i++)
    {
        if (k % i == 0)
            return 0;
    }
    return 1;
}
int getFactors(int factors[], int n)
{
    int cnt = 0;
    int k;
    for (k = 2; k <= n; k++)
    {
        if (isPrime(k) && n % k == 0)
        {
            factors[cnt++] = k;
            n /= k;
            while (n % k == 0)
            {
                factors[cnt++] = k;
                n /= k;
            }
        }
    }
    return cnt;
}
int output(int factors[], int cnt)
{
    int i;
    printf("%d", factors[0]);
    for (i = 1; i < cnt; i++)
        printf("*%d", factors[i]);
    putchar('\n');
    return 0;
}
int main()
{
    int factors[100];
    int T, n, cnt, j;
    scanf("%d", &T);
    for (j = 0; j < T; j++)
    {
        scanf("%d", &n);
        cnt = getFactors(factors, n);
        printf("%d=", n);
        output(factors, cnt);
    }
    return 0;
}

案例的输出都没有问题的

问了老师说在 getFactors()函数里while (n % k == 0)这个语句少了个条件 还说了句“比如9“莫名其妙的..也不知道他说的这个9是什么意思。谁能帮我分析一下


解决了。。我老师最开始秒回我就是说sqrt(n) 但是由于没有输出最后一项,我就把这段放在循环之前建一个变量了,这样只是第一次的循环减少了,而后面n还在变小,所以还是超时,再去问老师,他也糊涂了..就说while里改一下。其实改成sqrt(n)然后在最后加一个if(n!=1)factors[cnt++] = n;就对了。另外isPrime()这个函数可以去掉。

c c++

1个回答

你们老师信口一胡说,这个就不要理会了。你的问题在于,素数计算效率太低。
另外for (i = 2; i <= sqrt(k); i++)
这个不可靠,因为sqrt(k)可能因为精度误差,导致i漏掉一些数字

tilblackout
tilblackout AC了,问题在于k <= n改成k<=sqrt(n) 但是如果n本身是最后一个因子就不输出 只要最后判断一下 if(n!=1) factors[cnt++] = n;就好了
一年多之前 回复
tilblackout
tilblackout 好像真不是判断素数的问题 我发现不需要判断素数 因为从2开始 如果有不是素数的已经被分解了。我把那个函数去了下面直接if (n % k == 0) 仍然超时。说明应该真的不是判断素数的问题。
一年多之前 回复
tilblackout
tilblackout 抱歉看错了..不过素数计算效率怎为什么会低呢。需要怎么改进。
一年多之前 回复
tilblackout
tilblackout 我觉得你在胡说..这个地方我改过floor(sqrt(n)+0.5) 一样错 而且我说了是time limit exceed 如果问题出在这里也是wrong answer
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问