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.
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. 😃
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.
actually its the wrong code which I is wrote at first. the code I submitted is the following which I believe is time efficient:
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.
The code, you wrote gives wrong answer because, there are 3401 primes with their power less than or equal to 10^18.
mahawarvishal10 last updated on Dec. 17, 2020, 6:30 p.m.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.