tilblackout
lforat
2018-11-23 15:23

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

  • c++
  • c

图片说明

 #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()这个函数可以去掉。

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答