Алгоритм вычисления количества делителей заданного числа - PullRequest
Новая
       25

Алгоритм вычисления количества делителей заданного числа

166 голосов
/ 21 сентября 2008

Какой будет наиболее оптимальный (с точки зрения производительности) алгоритм для вычисления числа делителей заданного числа?

Было бы замечательно, если бы вы предоставили псевдокод или ссылку на какой-нибудь пример.

РЕДАКТИРОВАТЬ: Все ответы были очень полезны, спасибо. Я внедряю «Сито Аткина», а затем я собираюсь использовать нечто похожее на то, что указал Джонатан Леффлер. Ссылка Джастина Бозонье содержит дополнительную информацию о том, что я хотел.

Ответы [ 28 ]

76 голосов
/ 21 сентября 2008

Дмитрий прав, что вы хотите, чтобы «Сито Аткина» сформировало прайм-лист, но я не верю, что это решает весь вопрос. Теперь, когда у вас есть список простых чисел, вам нужно увидеть, сколько из этих простых чисел действует как делитель (и как часто).

Вот некоторый питон для алгоритма Посмотрите здесь и найдите «Тема: математика - алгоритм делителей потребности». Просто посчитайте количество элементов в списке, а не возвращайте их.

Вот доктор Математика , который объясняет, что именно вам нужно делать математически.

По существу, это сводится к тому, если ваш номер n:
n = a^x * b^y * c^z
(где a, b и c - простые делители n, а x, y и z - количество повторений делителя) тогда общее количество для всех делителей будет:
(x + 1) * (y + 1) * (z + 1).

Редактировать: Кстати, чтобы найти a, b, c и т. Д., Вы захотите сделать то, что составляет жадный алгоритм, если я правильно понимаю. Начните с вашего наибольшего простого делителя и умножайте его до тех пор, пока дальнейшее умножение не превысит число n. Затем перейдите к следующему наименьшему коэффициенту и умножьте на предыдущее простое число ^ количество раз, которое он умножил на текущее простое число, и продолжайте умножать на простое число, пока следующее не превысит n ... и т. Д. делители вместе и применить эти числа в формуле выше.

Не уверен на 100% в моем описании алгоритма, но если это не так, это что-то похожее.

47 голосов
/ 21 сентября 2008

Существует много техник для факторинга, чем сито Аткина. Например, предположим, что мы хотим вычислить 5893. Хорошо, его sqrt равно 76,76 ... Теперь мы попробуем написать 5893 как произведение квадратов. Скважина (77 * 77 - 5893) = 36, то есть 6 в квадрате, поэтому 5893 = 77 * 77 - 6 * 6 = (77 + 6) (77-6) = 83 * 71. Если бы это не сработало, мы бы посмотрели, было ли 78 * 78 - 5893 идеальным квадратом. И так далее. С помощью этой техники вы можете быстро проверить факторы около квадратного корня из n гораздо быстрее, чем проверяя отдельные простые числа. Если вы скомбинируете эту технику для исключения больших простых чисел с помощью сита, у вас будет намного лучший метод факторинга, чем с одним ситом.

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

Поэтому, если вы не имеете дело с маленькими целыми числами, я бы не пытался решить эту проблему сам. Вместо этого я бы попытался найти способ использовать что-то вроде библиотеки PARI , в которой уже реализовано высокоэффективное решение. При этом я могу вычислить случайное 40-значное число, например 124321342332143213122323434312213424231341, примерно за 0,05 секунды. (Его факторизация, на случай, если вам интересно, составляет 29 * 439 *1321* 157907 * 284749 * 33843676813 * 4857795469949. Я совершенно уверен, что с помощью решета Аткина это не удалось выяснить

33 голосов
/ 23 марта 2011

@ Yasky

Ваша функция делителей имеет ошибку в том, что она не работает правильно для идеальных квадратов.

Попытка: 

int divisors(int x) {
    int limit = x;
    int numberOfDivisors = 0;

    if (x == 1) return 1;

    for (int i = 1; i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            if (limit != i) {
                numberOfDivisors++;
            }
            numberOfDivisors++;
        }
    }

    return numberOfDivisors;
}
27 голосов
/ 23 сентября 2008

Я не согласен с тем, что сито Аткина - это путь, потому что проверка каждого числа в [1, n] на простоту может занять больше времени, чем уменьшение числа делением.

Вот код, который, хотя и немного хакерский, но в целом гораздо быстрее: 

import operator
# A slightly efficient superset of primes.
def PrimesPlus():
  yield 2
  yield 3
  i = 5
  while True:
    yield i
    if i % 6 == 1:
      i += 2
    i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
  d = {}
  primes = PrimesPlus()
  for p in primes:
    while n % p == 0:
      n /= p
      d[p] = d.setdefault(p, 0) + 1
    if n == 1:
      return d
def NumberOfDivisors(n):
  d = GetPrimeDecomp(n)
  powers_plus = map(lambda x: x+1, d.values())
  return reduce(operator.mul, powers_plus, 1)

ps Это рабочий код Python для решения этой проблемы.

10 голосов
/ 04 ноября 2008

Этот интересный вопрос гораздо сложнее, чем кажется, и на него не было ответа. Вопрос можно разделить на 2 очень разных вопроса.

1 дано N, найдите список L из простых факторов N

2 с учетом L, рассчитать количество уникальных комбинаций

Все ответы, которые я вижу до сих пор, относятся к № 1, и я не могу упомянуть, что он не поддается огромным количествам. Для N среднего размера, даже для 64-битных чисел, это легко; для огромного N проблема факторинга может быть «навсегда». От этого зависит шифрование с открытым ключом.

Вопрос № 2 требует дальнейшего обсуждения. Если L содержит только уникальные числа, это простой расчет с использованием формулы комбинации для выбора k объектов из n элементов. На самом деле, вам нужно суммировать результаты применения формулы при изменении k от 1 до sizeof (L). Однако L обычно будет содержать несколько вхождений нескольких простых чисел. Например, L = {2,2,2,3,3,5} является факторизацией N = 360. Теперь эта проблема довольно сложная!

Возвращаясь к # 2, для данной коллекции C, содержащей k элементов, такой, что у элемента a есть дубликаты, а у элемента b дубликаты b и т. Д. Сколько существует уникальных комбинаций от 1 до k-1 элементов? Например, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} должны появляться каждый раз и только один раз, если L = {2,2 , 2,3,3,5}. Каждая такая уникальная подколлекция является уникальным делителем N путем умножения элементов в подколлекции.

9 голосов
/ 21 сентября 2008

Ответ на ваш вопрос сильно зависит от размера целого числа. Методы для небольших чисел, например менее 100 бит, а для чисел ~ 1000 бит (например, используемых в криптографии) совершенно разные.

8 голосов
/ 05 апреля 2013

Вот прямой алгоритм O (sqrt (n)). Я использовал это, чтобы решить проект Эйлера 

def divisors(n):
    count=2 # accounts for 'n' and '1'
    i=2
    while(i**2 < n):
        if(n%i==0):
            count+=2
        i+=1
    count+=(1 if i**2==n else 0)
    return count
6 голосов
/ 11 ноября 2011

ТОЛЬКО одна строка
Я очень тщательно продумал ваш вопрос и попытался написать очень эффективный и производительный фрагмент кода. Чтобы вывести на экран все делители заданного числа, нам понадобится всего одна строка кода! (используйте опцию -std = c99 при компиляции через gcc) 

for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number

для определения числа делителей вы можете использовать следующую очень очень быструю функцию (работает правильно для всех целых чисел, кроме 1 и 2) 

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return counter;
}

или если вы рассматриваете данное число как делитель (работайте правильно для всех целых чисел, кроме 1 и 2) 

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

ПРИМЕЧАНИЕ: две вышеуказанные функции работают правильно для всех положительных целых чисел, кроме чисел 1 и 2 так что это функционально для всех чисел, которые больше 2 но если вам нужно охватить 1 и 2, вы можете использовать одну из следующих функций (чуть медленнее) 

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    if (n==2 || n==1)
    {
    return counter;
    }
    return ++counter;
}

OR 

int number_of_divisors(int n)
{
    int counter,i;
for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

маленький - это прекрасно :)

5 голосов
/ 02 февраля 2010

Как только у вас есть основная факторизация, есть способ найти количество делителей. Добавьте по одному к каждому из показателей для каждого отдельного фактора и затем умножьте их вместе.

Например: 36 Прайм Факторизация: 2 ^ 2 * 3 ^ 2 Делители: 1, 2, 3, 4, 6, 9, 12, 18, 36 Количество делителей: 9

Добавить по одному на каждый показатель степени 2 ^ 3 * 3 ^ 3 Умножить показатели: 3 * 3 = 9

5 голосов
/ 18 июля 2009

Вы можете попробовать это. Это немного хакерски, но довольно быстро. 

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)
Страница:
...