DEV Community

loading...

Time limit excedeed error for large values

Shrey Tripathi
Hi, I am Shrey Tripathi. Familiar with C, C++, Python, and Java. I also build web applications in Django and Flask, and currently learning Javascript. Occasionally, I also make games in Unity.
・1 min read

I have been given x and k, where x is the number of factors of a number A, and k is the number of prime factors of A. Given x and k, I have to find out whether such an A exists.
For example

INPUT : 4 2 
OUTPUT : 1

Since 6 is a number that has 4 factors 1, 2, 3, 6 out of which 2 are prime(2, 3).
Also it is given that x and k can have any values between 1 and 10^9.
Here is my code for the same :

long long int x, k;
scanf("%lld%lld", &x, &k);

int ans = 0;

bool stop = false;

for(long long int numbers=1; numbers<pow(10, 9) && !stop; numbers++)
{
    long long int noOfFactors = 0, noOfPrimes = 0;
    for(long long int a=1; a<=numbers && !stop; a++)
    {
        if(numbers%a == 0)
        {
            noOfFactors += 1;
            if((isprime(a)) == 1)
            {
                noOfPrimes += 1;
            }
         }
     }
     if(noOfFactors == x && noOfPrimes == k )
     {
         ans = 1;
         stop = true;
     }
     else ans = 0;
}   
printf("%d\n", ans);

Where isprime(x) returns 1 if x is prime else 0.

But while running the program, it shows TLE error.
Can anyone help me out in optimising this algorithm, or if any other method exists, can you just explain it to me ?
Any help in optimising this algorithm or using another method would be kindly appreciated.

Discussion (0)