yes i know that , i also made the accepted solution using that , but i am interested in getting divisor of a number using pf .
Okay thenI try dividing that number with prime numbers which are less than sqrt(value).
If we do brute force loop till sqrt(N) then complexity is sqrt(N). but If we just check primes less than sqrt(N) then it is O(sqrt(N)/10) this was my hack. I think this might not be the official soln.
Hence execution time might reduce to /10.
I think you are saying the same . Did you check my sample code for pf . Here it is fQZFMk - Online C++0x Compiler & Debugging Tool - Ideone.com .
1 Like
Maybe this works as well.
yeah ! So if a number is composite , the inner while loop will reduce my number , and the sqrt(n) will also get further reduced . But if a number is prime itself , then inner while loop won’t run and my complexity in worst case will be sqrt(n) . How will you achieve sqrt(n)/10 in this case .
I precompute all prime numbers before hand and push them into a vector (let’s say vector v) (using sieve).
PS: This is useful when we want to factorize more than 10 numbers.
We had to factorize 15 different numbers in the que which was discussed in this thread.
Then for each test case i do
for(int i=0;v[i]<=sqrt(n);i++)
while(n%v[i]==0)
n/=v[i];
1 Like
What about the pf greater than the sqrt(n) . It will itself be prime right ? .
1 Like
right \hspace{0mm}
Thanx . By the way what’s your cf handle name ?
smit_mandavia \hspace{0mm}
welcome
Such a Genius 
You’re joking 
\hspace{0mm}
results announced…,.,.,.,.,.,.,
where we can see the rank?? they just send me the mail of shortlisting wtf??
yes same here…,.,.,.,.,
in mockvita the results and ranks are showcase on TCS codevita site…Now it will not open for login…I’m so desperate to see my rank…XD
Used sqrt method to found all the divisor and created two list one containing divisor in ascending order and other in descending order . printed 2nd list in descending order . I got this solution passed after 2-3 attempts 
I did exactly same but got TLE 
Do in C they have supercomputer