583 TLE

[cse.mehedi]

I am getting TLE. Any 1 help me 2 solve.

Code: Select all

#include<stdio.h>
#include<math.h>
int isPrime(long n)
{
    long i,len=sqrt(n);
    for(i=2;i<=len;i++)
    {
        if(n%i==0)
        return 0;
    }
    return 1;
}
void recurtion(long n)
{
    if(n<2) return 0;
    long i,len;
            for(i=2;;i++)
            {
                if(n%i==0)
                {
                    if(isPrime(i)==1)
                    {
                        printf(" x");
                        printf(" %ld",i);
                        recurtion(n/i);
                        break;
                    }
                }
            }
}

void main()
{
    long i,n,len;
    while(scanf("%ld",&n)==1)
    {
        if(n==0) break;
        if(n==1) printf("1 = 1\n");
        else if(n==-1) printf("1 = -1 x 1\n");
        else {
        if(n<0) {printf("%ld = -1 x",n);n*=-1;}
        else printf("%ld =",n);
        for(i=2;;i++)
        {
            if(n%i==0 && isPrime(i)==1)
            {
                len=n/i;
                printf(" %ld",i);
                break;
            }
        }
        recurtion(len);
        printf("\n");
        }
    }
}




[brianfry713]

Use a sieve to precompute the primes.
http://acm.uva.es/board/viewtopic.php?t=3170