Подсчитать количество делителей для всех чисел до N

Question

Мне нужно посчитать все делители для каждого числа в диапазоне 1 to n, Я записал ниже реализацию для, учитывая целое число numподсчитывает количество делителей num, Его сложность O(sqrt(n)), Таким образом, по всей сложности оказывается O(n * sqrt(n)), Это может быть уменьшено? Если ДА, то можете ли вы дать алгоритм для этого?

КОД:

 public static int countDivisors(int num)
    {
        int limit = (int)Math.sqrt(num);
        int count = 2;
        for(int i = 2 ; i <= limit ; i++)
        {
            if(num % i == 0)
            {
                count++;
                if(num / i != i)
                {
                    count++;
                }
            }
        }
        return count;
    }

PS:
Эта функция будет вызвана n раз.

Answer 1

Вы можете улучшить наивный подход, используя своего рода обобщенное сито Эратосфена. Вместо того, чтобы просто помечать число как составное, также сохраните первый найденный вами делитель (я делаю это в функции computeDivs ниже).

class Main
{
    // using Sieve of Eratosthenes to factorize all numbers
    public static int[] computeDivs(int size) {
      int[] divs = new int[size + 1];
      for (int i = 0; i <  size + 1; ++i) {
        divs[i] = 1;
      }
      int o = (int)Math.sqrt((double)size);
      for (int i = 2; i <= size; i += 2) {
        divs[i] = 2;
      }

      for (int i = 3; i <= size; i += 2) {
        if (divs[i] != 1) {
          continue;
        }
        divs[i] = i;
        if (i <= o) {
          for (int j = i * i; j < size; j += 2 * i) {
            divs[j] = i;
          }
        }
      }
      return divs;
    }

    // Counting the divisors using the standard fomula
    public static int countDivisors(int x, int[] divs) {
      int result = 1;
      int currentDivisor = divs[x];
      int currentCount = 1;
      while (currentDivisor != 1) {
        x /= currentDivisor;
        int newDivisor = divs[x];
        if (newDivisor != currentDivisor) {
          result *= currentCount + 1;
          currentDivisor = newDivisor;
          currentCount = 1;
        } else {
          currentCount++;
        }
      }
      if (x != 1) {
        result *= currentCount + 1;
      }

      return result;
    }


    public static int countAllDivisors(int upTo) {
      int[] divs = computeDivs(upTo + 1);
      int result = 0;
      for (int i = 1; i <= upTo; ++i) {
        result += countDivisors(i, divs);
      }
      return result;

    }

    public static void main (String[] args) throws java.lang.Exception {
      System.out.println(countAllDivisors(15));
    }
}

Вы также можете увидеть код, выполненный на ideone здесь.

Короче говоря, я использую сито для вычисления наибольшего простого множителя для каждого числа. Используя это, я могу очень эффективно вычислить разложение факторов каждого числа (и я использую это в countDivisors).

Трудно рассчитать сложность сита, но стандартная оценка O(n * log(n)), Также я уверен, что эту сложность улучшить невозможно.

Answer 2

Вы можете сделать намного лучше, чем O(n.sqrt(n)) с помощью простой итерации. Код написан на C++, но вы можете легко понять идею.

#include <iostream>
#include <vector>
using namespace std;

void CountDivisors(int n) {
    vector<int> cnts(n + 1, 1);
    for (int i = 2; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            cnts[j]++;
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << cnts[i] << " \n"[i == n];
    }
}

int main() {
    CountDivisors(100);
    return 0;
}

Продолжительность n/1 + n/2 + n/3 + n/4 + ... + n/n который может быть аппроксимирован O(nH(n)), где H(n) это гармонический ряд. Я думаю, что значение не больше, чем O(nlog(n)),

Answer 3

Использование итерации допустимо для относительно небольших чисел. Как только количество делителей становится больше (более 100-200), итерация будет занимать значительное время.

Лучшим подходом было бы подсчитать количество делителей с помощью простой факторизации числа.

Итак, выразите число с простой факторизацией следующим образом:

        public static List<Integer> primeFactorizationOfTheNumber(long number) {
    List<Integer> primes = new ArrayList<>();
    var remainder = number;
    var prime = 2;

    while (remainder != 1) {
      if (remainder % prime == 0) {
        primes.add(prime);
        remainder = remainder / prime;
      } else {
        prime++;
      }
    }
    return primes;
  }

Затем, учитывая простую факторизацию, выразить ее в форме экспоненты, получить экспоненты и добавить каждому из них. Далее умножьте полученные числа. Результатом будет количество делителей числа. Подробнее об этом здесь .

        private long numberOfDivisorsForNumber(long number) {
    var exponentsOfPrimeFactorization = primeFactorizationOfTheNumber(number)
      .stream()
      .collect(Collectors.groupingBy(Integer::intValue, Collectors.counting()))
      .values();
    return exponentsOfPrimeFactorization.stream().map(n -> n + 1).reduce(1L, Math::multiplyExact);
  }

Этот алгоритм работает очень быстро. Для меня он находит число с 500 делителями менее чем за секунду.