AboAlmanal_ReLoad's blog

By AboAlmanal_ReLoad, history, 6 weeks ago, In English

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?

Thanks in advance!

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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   Vote: I like it +26 Vote: I do not like it

    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, # ^ |
        Vote: I like it +32 Vote: I do not like it

      And don't you hate how GeeksForGeeks links come up as the first results for all the algorithm related google searches?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it -17 Vote: I do not like it

yes but only if p=np

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

In addition, the number of theses segments is equal to the number of factors of N.

No. Take any large prime.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      Since the largest prime factor pair of a composite number is less than or equal to $$$\sqrt N$$$.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That isn't right. Take 14, 7 is a prime factor larger than sqrt(14) ~ 3.74

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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, # |
  Vote: I like it -13 Vote: I do not like it

Is it Rated ?