Насколько быстро работает этот простой алгоритм факторизации?

Question

Я хочу понять сложность этого кода:

prime_factorize(N) {

   for (int i = 2; i <= N; i++) {
       while (N % i == 0) {
           print i
           N = N / i
        }
    }
}

На самом деле это не язык программирования - это просто псевдокод.

Я знаю что делает псевдокод. Он делит все факторы на 2, а затем на 3 и т. Д. c. Я также знаю, что код можно оптимизировать только до go до sqrt(N), но я хочу выяснить время выполнения кода в том виде, в котором я его опубликовал. это квадрати c, я уверен, что это неправильно. Причина, по которой я считаю это неправильным, заключается в том, что я знаю, что алгоритм первичного сита работает в O(nloglogn) времени, и он чем-то напоминает этот алгоритм.

Может кто-нибудь помочь мне проанализировать этот алгоритм?

Answer 1

Легко видеть, что этот алгоритм работает в O (n) в худшем случае.

Вам просто нужно рассмотреть случай, когда n - простое число, тогда i будет повторяться до тех пор, пока N.

То же самое происходит, если N не простое число. Возьмем N = 2 * 53 в качестве примера. Это займет 53 итерации = O (N / 2) = O (N).