< Back to forum

REC15B - A query

The problem basically states we have to calculate the number of i's for (i=1;i<=n;i++) which has 5 factors. During the contest I worked out and found that all prime numbers to the power 4 only had 5 factors. That means 2^4=16, 3^4=81, 5^4=625, and so on. However I got Time limit exceeded also in my perspective the code is efficient. Later on I found out that the tutorial also stated the same logic. Please help me and explain why my code showed TLE???

My code:

include

using namespace std;

int main()

{ long long int t,n,count,c,s;

cin>>t;
while (t--)
{
    cin>>n;
    count=0;
    c=2;
    s=pow(c,4);
    while(s<=n)
    {
        count++;
        c++;
        s=(pow(c,4));
    }
    cout<<count<<endl;
}
return 0;

}

Asked by: akshaydgp2015 on Dec. 17, 2020, 4:22 p.m. Last updated on Dec. 17, 2020, 4:22 p.m.


Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

In this method, you will be traversing on all numbers from 2 to some number, power 4 of which is just less than or equal to n. And, this will be followed for every test case. This is gonna be a lot of operations anyways.

The number of times, you will be counting for each test case can go as high as 10^(18/4), and doing that for every test case (10^5 test cases), would make the total number of operations equal to 10^(9.5). Also, you need to be sure that c is a prime before increasing counter.

Now, in order to compute primes, whose power 4 is less than 10^18 (max value of n). You should use Sieve of Eratosthenes. Using sieve, you can store the numbers which are prime to the power 4 and use binary search to find the number of numbers less than and equal to n.

Hope it helps. 😃

mahawarvishal10 last updated on Dec. 17, 2020, 4:59 p.m. 1    Reply    Upvote   

avatar

If you are having problems in understanding these topics, don't worry, these topics will be covered in RECursion classes.

mahawarvishal10 last updated on Dec. 17, 2020, 5:02 p.m.

avatar

actually its the wrong code which I is wrote at first. the code I submitted is the following which I believe is time efficient:

include

using namespace std;

int main()

{ long long int t,n,count,c,s; cin>>t;

int p[168]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
while (t--)
{
    cin>>n;
    count=0;
    c=0;
    s=pow(p[c],4);
    while(s<=n)
    {
        count++;
        c++;
        s=(pow(p[c],4));
    }
    cout<<count<<endl;
}
return 0;

}

Yes I got ur comment. Maybe I got WA because this takes care only till (10^4) ^4=10^16.

akshaydgp2015 last updated on Dec. 17, 2020, 5:35 p.m.

avatar

The code, you wrote gives wrong answer because, there are 3401 primes with their power less than or equal to 10^18.

Now, iterating over 3401 primes, in each test case, can still lead to TLE. In that case, you can use binary search.

And for storing all the primes, you may precompute them, but, doing it with sieve will be better.

mahawarvishal10 last updated on Dec. 17, 2020, 6:30 p.m.

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.