Shrey Tripathi

Posted on

# Time limit excedeed error for large values

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.