Я не знаю наиболее эффективный метод, но я сделал бы следующее:

• Составляют таблицу начал для нахождения всех начал меньше чем или равными квадратному корню числа (Лично, я использовал бы Решето Atkin)
• количество все начала, меньше чем или равные квадратному корню числа, и умножьте это на два. Если квадратный корень числа является целым числом, то вычтите один из переменной количества.

Должен работать \o /

, Если Вам нужно, я могу кодировать что-то завтра в C для демонстрации.

Это не просто вопрос факторинга числа - определение всех факторов числа? Можно тогда решить, нужны ли Вам все комбинации одного или нескольких факторов.

Так, один возможный алгоритм был бы:

factor(N)
    divisor = first_prime
    list_of_factors = { 1 }
    while (N > 1)
        while (N % divisor == 0)
            add divisor to list_of_factors
            N /= divisor
        divisor = next_prime
    return list_of_factors

тогда ваше дело комбинировать факторы для определения остальной части ответа.

Вы хотите Решето Atkin, описанного здесь: http://en.wikipedia.org/wiki/Sieve_of_Atkin

Решето Atkin является оптимизированной версией решета Эратосфена, которое дает всем простым числам до данного целого числа. Необходимо быть в состоянии погуглить это для большего количества детали.

, Как только у Вас есть тот список, это - простой вопрос для деления числа на каждое начало, чтобы видеть, является ли это точный делитель (т.е. остаток является нулем).

основные шаги, вычисляющие делители для номера (n), [это - псевдокод, преобразованный из реального кода, таким образом, я надеюсь, что у меня нет допущенных погрешностей]:

for z in 1..n:
    prime[z] = false
prime[2] = true;
prime[3] = true;

for x in 1..sqrt(n):
    xx = x * x

    for y in 1..sqrt(n):
        yy = y * y

        z = 4*xx+yy
        if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)):
            prime[z] = not prime[z]

        z = z-xx
        if (z <= n) and (z mod 12 == 7):
            prime[z] = not prime[z]

        z = z-yy-yy
        if (z <= n) and (x > y) and (z mod 12 == 11):
            prime[z] = not prime[z]

for z in 5..sqrt(n):
    if prime[z]:
        zz = z*z
        x = zz
        while x <= limit:
            prime[x] = false
            x = x + zz

for z in 2,3,5..n:
    if prime[z]:
        if n modulo z == 0 then print z

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

• общий обзор: http://en.wikipedia.org/wiki/Divisor_function

• значения для маленького n и некоторые полезные ссылки: A000005: d (n) (также названный tau (n) или sigma_0 (n)), количество делителей n.

• реальный пример: факторизация целых чисел

Этот интересный вопрос намного более труден, чем это смотрит, и этому не ответили. Вопрос может быть включен в 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 объекты, такие, что объект' дубликаты и объект 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 путем умножения объектов в поднаборе.

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

Вот некоторый код, который, хотя немного hackier, обычно намного быстрее:

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 для решения этой проблемы.

Существуют партия [еще 114] методы к факторингу, чем решето Atkin. Например, предположите, что мы хотим к фактору 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 намного быстрее, чем путем тестирования отдельных начал. При объединении этой техники для исключения больших начал с решетом у Вас будет намного лучший метод факторинга, чем с решетом одним.