@l_returns you r making use of sieve for effectively finding the prime factors . But
for e.g if no is 1125899906842597 (hope this is prime)
then precomputing primes till sqrt(10^15) only ,how u will know its prime factors
either u build sieve till 10^15 (not possible) or find the prime factors using less effective algo
P.S correct me if i am wrong
Even if you can do somehow ,then finding all prime factors also takes worst case O(sqrt(n)). Which is same as finding all the divisors.
Bro here is the simple brute Force approach which completely passes all the test case ( it really sucks)
//Divine Divisors*
#include <stdio.h>
int main()
{
int test;
scanf("%d",&test);
for(int j=0; j<test ; j++)
{
long long int number, i;
scanf("%lld",&number);
for(i=1; i <= number; ++i)
{
if (number%i == 0)
{
printf("%lld ",i);
}
}
printf("\n");
}
return 0;
}
Bro there is another approach which is in cbrt(n) complexity but it is difficult for me,
PS : codevita is just about language game
The sqrt(n) approach in Python or in cpp gets TLE , but o(n) complexity accepted in C wtf
Have any one listened about pollard rho which is O(n^1/4) for integer factorization
If I know it earlier I definately code in CâŚ
Or Kya Bhai Matlab itni bevkufi h tcs walo ki same approach agar cpp ya Python me chalao to tle c me chalao to accepted wahhhâŚ
this approach is too naiveâŚjust shock to hear that it was ACâŚNow I feel guiltyâŚ:)
How can you find primes more than 10^6 using seive? It would work if N<= 10^12. I think it needs pollard rho for finding further prime and then as you said finding divisors using recursion.
Correct me anytime?,
One of my friendâs solution is accepted square root of n complexity but he is the trick when was printing the the divisors increment i with one instead of incrementing one, a basic observation is required if a number is even then its divisor maybe even or maybe odd but if a number is is odd then definitely the divisors are odd so instead of incrementing i by 1 we incrementing by 2 so sqrt(n)/2 complexity
And it accepted.
I was guessing they need minor optimisation to solve that. But couldnât figure out that I have to optimize just by a factor of 2(bcz itâs same sqrn(n) now).
They should atleast provide the time limit, so that we can calculate what level of optimisation they want.
BtwâŚthis solution should also fail, bcz in worst case if u take t=15, and n=10^15 for all case, ur solution will be sqrt(n).
So what can i predict? Weak test cases for their cheap optimisation?
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(tâ)
{
vector< long int > v;
long int n;
cin>>n;
int c=2;
long int sq=sqrt(n);
for(long int i=2;i<=sq;i++)
{
if(n%i==0)
{
c++;
v.push_back(i);
if(i!=n/i)
{
c++;
v.push_back(n/i);
}
}
}
if(n==1) cout<<1<<"\n" ;
else
{
v.push_back(1);
v.push_back(n);
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
}
cout<<"\n";
}
}
This somehow passedâŚ!!
but when i give all 15 inputs as 10^15 âŚit gives TLE
Okay I forgot that. But fact is we can declare array upto size 10^8.
That was my point.
Read my answer again. I said find power of those prime as well.
After dividing it with all primes till sqrt(10^15)
If number is > 1 then it will be a prime number only.
You can do that. Google how to find prime factors of a number in O(sqrt(n)) you will see how we can find those factors which are >sqrt(n)
R u asking me or telling me ?
In case you are asking then this is my answer :
Nope. It wonât take sqrt(n) will be much less because we will be check only prime numbers less than sqrt(n). That divides complexity by 10-20 times. Which should pass in given constraints.
Exactly. \hspace{0mm}