Подсчет делителей чисел до N в O (N)?

Вот простая оптимизация решения @גלעד ברקן. Вместо того, чтобы использовать наборы, используйте массивы. Это примерно в 10 раз быстрее, чем установленная версия.

n = 100

answer = [None for i in range(0, n+1)]
answer[1] = 1

small_factors = [1]
p = 1
while (p < n):
    p = p + 1
    if answer[p] is None:
        print("\n\nPrime: " + str(p))
        limit = n / p
        new_small_factors = []
        for i in small_factors:
            j = i
            while j <= limit:
                new_small_factors.append(j)
                answer[j * p] = answer[j] + answer[i]
                j = j * p
        small_factors = new_small_factors

print("\n\nAnswer: " + str([(k,d) for k,d in enumerate(answer)]))

Стоит отметить, что это также алгоритм перечисления простых чисел за O(n). Однако с помощью колеса, сгенерированного из всех простых чисел размером меньше log(n)/2, можно создать список простых чисел за время O(n/log(log(n))).

Как насчет этого? Начните с простого числа 2 и сохраните список кортежей, (k, d_k), где d_k — количество делителей k, начиная с (1,1):

for each prime, p (ascending and lower than or equal to n / 2):
  for each tuple (k, d_k) in the list:
    if k * p > n:
      remove the tuple from the list
      continue
    power = 1
    while p * k <= n:
      add the tuple to the list if k * p^power <= n / p
      k = k * p
      output (k, (power + 1) * d_k)
      power = power + 1
  the next number the output has skipped is the next prime
  (since clearly all numbers up to the next prime are
   either smaller primes or composites of smaller primes)

Приведенный выше метод также генерирует простые числа, полагаясь на O(n) памяти, чтобы продолжать поиск следующего простого числа. Имея более эффективный, независимый поток простых чисел, мы могли бы избежать добавления каких-либо кортежей (k, d_k) в список, где k * next_prime > n, а также освободить всю память, содержащую выходные данные, превышающие n / next_prime.

код

Рассмотрим общее количество этих подсчетов, sum(phi(i) for i=1,n). Эта сумма равна O(N log N), поэтому любое O(N) решение должно будет обходить индивидуальный подсчет.

Это говорит о том, что любое улучшение должно зависеть от предыдущих результатов (динамическое программирование). Мы уже знаем, что phi(i) — это произведение каждой простой степени плюс единица. Например, 12 = 2^2 * 3^1. Степени 2 и 1 соответственно. (2+1)*(1+1) = 6. У 12 6 делителей: 1, 2, 3, 4, 6, 12.

Это «сводит» вопрос к тому, можете ли вы использовать априорные знания, чтобы получить O(1) способ прямого вычисления количества делителей, без необходимости подсчитывать их по отдельности.

Подумайте о данном случае... количество делителей до сих пор включает:

1 1
2 2
3 2
4 3
6 4

Есть ли O(1) способ получить phi(12) = 6 из этих цифр?

Вот алгоритм, который теоретически лучше, чем O(n log(n)), но может быть хуже для разумного n. Я полагаю, что его время работы равно O(n lg*(n)), где lg* — это https://en.wikipedia.org/wiki/Iterated_logarithm.

Прежде всего, вы можете найти все простые числа до n за время O(n), используя решето Аткина. Подробнее см. https://en.wikipedia.org/wiki/Sieve_of_Atkin.

Теперь идея состоит в том, что мы создадим наш список счетчиков, вставляя каждый счетчик только один раз. Мы пройдемся по простым множителям один за другим и вставим значения для всего, что является максимальным простым числом. Однако для этого нам нужна структура данных со следующими свойствами:

1. Мы можем сохранить значение (в частности, количество) для каждого значения.
2. Мы можем пройтись по списку вставленных значений вперед и назад в O(1).
3. Мы можем найти последнее вставленное число ниже i "эффективно".
4. Вставка должна быть "эффективной".

(Цитаты — это части, которые трудно оценить.)

Первый тривиален: каждому слоту в нашей структуре данных нужно место для значения. Второе можно сделать с двусвязным списком. Третье можно сделать с умной вариацией списка пропусков. Четвертый выпадает из первых 3-х.

Мы можем сделать это с помощью массива узлов (которые не инициализированы) со следующими полями, которые выглядят как двусвязный список:

1. value Ответ, который мы ищем.
2. prev Последнее предыдущее значение, для которого у нас есть ответ.
3. next Следующее значение, для которого у нас есть ответ.

Теперь, если i находится в списке, а j является следующим значением, трюк с пропуском списка будет заключаться в том, что мы также заполним prev для первого даже после i, первого кратного 4, кратного 8 и так далее, пока мы не достигнем j. Итак, если i = 81 и j = 96, мы заполним prev вместо 82, 84, 88, а затем 96.

Теперь предположим, что мы хотим вставить значение v в k между существующими i и j. Как мы делаем это? Я представлю псевдокод, начиная с известного только k, а затем заполню его для i = 81, j = 96 и k = 90.

k.value := v
for temp in searching down from k for increasing factors of 2:
    if temp has a value:
        our_prev := temp
        break
    else if temp has a prev:
        our_prev = temp.prev
        break
our_next := our_prev.next
our_prev.next := k
k.next := our_next
our_next.prev := k
for temp in searching up from k for increasing factors of 2:
    if j <= temp:
        break
    temp.prev = k
k.prev := our_prev

В нашем конкретном примере мы хотели искать вниз от 90 до 90, 88, 80, 64, 0. Но на самом деле нам говорят, что prev это 81, когда мы добираемся до 88. Мы хотели бы искать до 90, 92, 96, 128, 256, ..., однако нам просто нужно установить 92.prev 96.prev, и все готово.

Теперь это сложный код, но его производительность O(log(k-i) + log(j-k) + 1). Это означает, что он начинается как O(log(n)), но становится лучше по мере заполнения большего количества значений.

Так как же нам инициализировать эту структуру данных? Итак, мы инициализируем массив неинициализированных значений, затем устанавливаем 1.value := 0, 1.next := n+1 и 2.prev := 4.prev := 8.prev := 16.prev := ... := 1. И затем мы начинаем обрабатывать наши простые числа.

Когда мы достигнем простого p, мы начнем с поиска предыдущего вставленного значения ниже n/p. Идя назад оттуда, мы продолжаем вставлять значения для x*p, x*p^2, ..., пока не достигнем предела. (Причина в обратном порядке заключается в том, что мы не хотим пытаться вставить, скажем, 18 один раз для 3 и один раз для 9. Обратный ход предотвращает это.)

Каково наше время работы? Нахождение простых чисел равно O(n). Поиск начальных вставок также легко O(n/log(n)) операций времени O(log(n)) для другого O(n). А как насчет вставки всех значений? Это тривиально O(n log(n)), но можем ли мы сделать лучше?

Ну, во-первых, все заполненные вставки с плотностью 1/log(n) могут быть выполнены за время O(n/log(n)) * O(log(n)) = O(n). И тогда все вставки с плотностью 1/log(log(n)) также могут быть выполнены за время O(n/log(log(n))) * O(log(log(n))) = O(n). И так далее с увеличением количества логов. Количество таких факторов, которое мы получаем, составляет O(lg*(n)) для оценки O(n lg*(n)), которую я дал.

Я не показал, что эта оценка настолько хороша, насколько это возможно, но я думаю, что это так.

Так что не O(n), но чертовски близко.