By AboAlmanal_ReLoad, history, 6 weeks ago,

Hello everyone, I was trying to solve CSES — Sum of Divisors and finally found a solution within a complexity of O(sqrt(N)), and it worked. However, the problem intrigued my interested so I searched about it on Google, and came across this article explaining a solution to the same problem but with a complexity of O(log2(n))! the observations mentioned in the article are exactly the same I used to build-up my solution, but I don't understand how they consider it as O(log2(n)) or if they are doing something different with the code that I don't get.

[SPOILER]
In regards of the problem, the main observation is that there are segments of numbers that within each segment, theses numbers will have the same number of occurrences in the total answer. In addition, the number of theses segments is equal to the number of factors of N. In conclusion, the problem is about finding the factorization of the number N (as I guess)

So, what is the most efficient way to find the factorization of a number N? what is the most efficient way to solve the problem? is there anything I am missing with the blog mentioned above?

• +12

 » 6 weeks ago, # |   +9 No, you cannot factor a number in O(number length), or even in any polynomial of number length. At least, no one knows how to do that. The quickest known algorithm is general number field sieve but it has a large constant and it's still superpolynomial.The article you linked to is wrong, their method is not $\mathcal{O}(\log n)$ but $\mathcal{O}(\sqrt{n})$. You can either use your brain to verify that or just try their algorithm on something like $10^{16}$ -- it takes it about 20 seconds.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +26 Classic geeksforgeeks...The article is littered with examples of trivialities, but the magic line i = n / (n / (i + 1)); which the complexity depends on is just completely unexplained. (It seems to go through all numbers of the form $\left \lfloor \frac{n}{i} \right \rfloor$, which is bounded below by $\sqrt{n}$.)
•  » » » 5 weeks ago, # ^ |   +32 And don't you hate how GeeksForGeeks links come up as the first results for all the algorithm related google searches?
•  » » » » 5 weeks ago, # ^ |   +31 The more frustrating thing is that they try to be the C++ reference and have a (pretty useless, much worse than either of the real references) page for just about every function in C++.All things considered I pretty strongly suspect that they use some sketchy techniques that manipulate the Google algorithm to show them on the top.
 » 6 weeks ago, # | ← Rev. 2 →   0 It's not known if integer factorization is in P. Sum of divisors is a bit easier problem but I haven't heard about the polynomial algorithm that solves it (maybe they are equivalent).
 » 6 weeks ago, # | ← Rev. 2 →   0 Yeah I'm also looking for a faster prime factorization algorithm. After reading cp-algorithms integer factorization I think polard rho or brent is the best.
 » 6 weeks ago, # |   -17 yes but only if p=np
•  » » 6 weeks ago, # ^ |   +13 Factorization is not known to be NP-complete. It may be in P even if P != NP.
•  » » » 6 weeks ago, # ^ |   0 interesting btw how to solve this problem https://codeforces.com/contest/993/problem/E?
•  » » » » 5 weeks ago, # ^ |   0 idea to solve problem
•  » » » » » 5 weeks ago, # ^ |   0 That's the joke.
 » 5 weeks ago, # |   +6 In addition, the number of theses segments is equal to the number of factors of N. No. Take any large prime.
•  » » 5 weeks ago, # ^ |   +1 You are completely right! I am a bit confused, how can we prove that the complexity of the solution is O(sqrt(N)) now?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Since the largest prime factor pair of a composite number is less than or equal to $\sqrt N$.
•  » » » » 5 weeks ago, # ^ |   0 That isn't right. Take 14, 7 is a prime factor larger than sqrt(14) ~ 3.74
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I was meant to say the prime factor pairs but yeah you get the idea.P.S. I actually tried to write that but I thought it's not a relevant word to express it.
 » 5 weeks ago, # |   -13 Is it Rated ?