No, upperbound of divisors of a number can be atmost n^1/3, so for n=10^15, max divisors can be 10^5 which can be stored easily
Suppose N=40; it has two prime factor 2,5. How can u generate with recursion/loop all it’s factors.
Ps: 20 is also a factor of it. Using loop how can u get 20 with 2 and 5.
So storing just prime factor won’t work.
@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)