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

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

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

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

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

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

По сути, это сводится к тому, что если ваше число 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% в моем описании алгоритма, но если это не так, то это что-то похожее.

Существует намного больше методов для факторинга, чем сито Аткина. Например, предположим, что мы хотим вычислить 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. Я совершенно уверен, что это не удалось выяснить с помощью сита Аткина ...)

@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;
}

Я не согласен с тем, что сито Аткина - это путь, потому что для проверки простоты каждого числа в [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 для решения этой проблемы.

Вот прямой алгоритм 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
    if i ** 2 == n:
        count += 1
    return count

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

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

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

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

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

ТОЛЬКО одна строка.
Я очень тщательно продумал ваш вопрос и попытался написать очень эффективный и производительный фрагмент кода. Чтобы вывести на экран все делители заданного числа, нам нужна всего одна строка кода! (используйте опцию -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;
}

ИЛИ

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;
}

маленький красивый :)

Сито Аткина - это оптимизированная версия сита Эратосфена, которая дает все простые числа до заданного целого числа. Вы должны быть в состоянии Google это для более подробной информации.

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

Основные этапы вычисления делителей для числа (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

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

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)

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

Например: 36 Prime Factorization: 2 ^ 2 * 3 ^ 2 Делители: 1, 2, 3, 4, 6, 9, 12, 18, 36 Количество делителей: 9

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

Перед тем, как принять решение, подумайте, что в типичном случае подход Sieve не может быть хорошим ответом.

Некоторое время назад возник главный вопрос, и я провел временный тест - по крайней мере, для 32-разрядных целых чисел было определено, является ли оно простым, медленнее, чем грубая сила. Существует два фактора:

1) В то время как человеку требуется некоторое время, чтобы выполнить деление, он очень быстро работает на компьютере - похоже на стоимость поиска ответа.

2) Если у вас нет основной таблицы, вы можете создать цикл, который полностью выполняется в кэше L1. Это делает это быстрее.

Это эффективное решение:

#include <iostream>
int main() {
  int num = 20; 
  int numberOfDivisors = 1;

  for (int i = 2; i <= num; i++)
  {
    int exponent = 0;
    while (num % i == 0) {
        exponent++; 
        num /= i;
    }   
    numberOfDivisors *= (exponent+1);
  }

  std::cout << numberOfDivisors << std::endl;
  return 0;
}

Делители делают что-то впечатляющее: они делят полностью. Если вы хотите проверить число делителей на число n, оно явно избыточно, чтобы охватить весь спектр 1...n. Я не провел каких-либо углубленных исследований для этого, но я решил проблему Проекта Эйлера 12 по треугольным числам . Мое решение для теста с делителем более 500 делилось на 309504 микросекунды (~ 0,3 с). Я написал эту функцию делителя для решения.

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

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

    return numberOfDivisors * 2;
}

У каждого алгоритма есть слабое место. Я думал, что это было слабым против простых чисел. Но так как треугольные числа не напечатаны, это послужило своей цели безупречно. Из моего профилирования я думаю, что все прошло хорошо.

Счастливых праздников.

Вы хотите Сито Аткина, описанное здесь: http://en.wikipedia.org/wiki/Sieve_of_Atkin

метод простых чисел здесь очень понятен. P [] - список простых чисел, меньших или равных sq = sqrt (n);

for (int i = 0 ; i < size && P[i]<=sq ; i++){
          nd = 1;
          while(n%P[i]==0){
               n/=P[i];
               nd++;
               }
          count*=nd;
          if (n==1)break;
          }
      if (n!=1)count*=2;//the confusing line :D :P .

     i will lift the understanding for the reader  .
     i now look forward to a method more optimized  .

Учебники теории чисел называют функцию подсчета числа делителей тау. Первый интересный факт заключается в том, что он мультипликативный, т.е. τ (ab) = τ (a) τ (b), когда a и b не имеют общего множителя. (Доказательство: каждая пара делителей a и b дает отдельный делитель ab).

Теперь отметим, что для простого числа τ (p ** k) = k + 1 (степени p). Таким образом, вы можете легко вычислить τ (n) из его факторизации.

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

1. Проверьте, является ли число простым (быстрым)
2. Если так, верните 2
3. В противном случае, факторизовать число (медленно, если несколько больших простых факторов)
4. Вычислить τ (n) из факторизации

Ниже приведена программа на C для определения числа делителей заданного числа.

Сложность вышеупомянутого алгоритма O (sqrt (n)).

Этот алгоритм будет работать правильно для числа, которое является идеальным квадратом, а также для чисел, которые не являются идеальным квадратом.

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

Обратите внимание, что сохранение верхнего предела в отдельной переменной также экономит время, вам не следует вызывать функцию sqrt в разделе условий цикла for, это также экономит ваше вычислительное время.

#include<stdio.h>
#include<math.h>
int main()
{
    int i,n,limit,numberOfDivisors=1;
    printf("Enter the number : ");
    scanf("%d",&n);
    limit=(int)sqrt((double)n);
    for(i=2;i<=limit;i++)
        if(n%i==0)
        {
            if(i!=n/i)
                numberOfDivisors+=2;
            else
                numberOfDivisors++;
        }
    printf("%d\n",numberOfDivisors);
    return 0;
}

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

for(i=2;i*i<=n;i++)
{
    ...
}

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

public static List<Integer> divisors(n) {   
    ArrayList<Integer> aList = new ArrayList();
    int top_count = (int) Math.round(Math.sqrt(n));
    int new_n = n;

    for (int i = 2; i <= top_count; i++) {
        if (new_n == (new_n / i) * i) {
            aList.add(i);
            new_n = new_n / i;
            top_count = (int) Math.round(Math.sqrt(new_n));
            i = 1;
        }
    }
    aList.add(new_n);
    return aList;
}

Это самый простой способ вычисления числа делителей:

class PrintDivisors
{
    public static void main(String args[])
    {

    System.out.println("Enter the number");

    // Create Scanner object for taking input
    Scanner s=new Scanner(System.in);

    // Read an int
    int n=s.nextInt();

        // Loop from 1 to 'n'
        for(int i=1;i<=n;i++)
        {

            // If remainder is 0 when 'n' is divided by 'i',
            if(n%i==0)
            {
            System.out.print(i+", ");
            }
        }

    // Print [not necessary]    
    System.out.print("are divisors of "+n);

    }
}

@Kendall

Я проверил ваш код и сделал некоторые улучшения, теперь он стал еще быстрее. Я также тестировал с кодом @ هومن جاویدپور, это также быстрее, чем его код.

long long int FindDivisors(long long int n) {
  long long int count = 0;
  long long int i, m = (long long int)sqrt(n);
  for(i = 1;i <= m;i++) {
    if(n % i == 0)
      count += 2;
  }
  if(n / m == m && n % m == 0)
    count--;
  return count;
}

Разве это не просто вопрос факторизации числа - определения всех факторов числа? Затем вы можете решить, нужны ли вам все комбинации одного или нескольких факторов.

Итак, один из возможных алгоритмов:

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

Затем вы должны объединить факторы, чтобы определить остальную часть ответа.

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

n=int(input())

a=[]
b=[]

def sieve(n):
    np = n + 1
    s = list(range(np)) 
    s[1] = 0
    sqrtn = int(n**0.5)
    for i in range(2, sqrtn + 1): 
        if s[i]:
            s[i*i: np: i] = [0] * len(range(i*i, np, i))
    return filter(None, s)

k=list(sieve(n))

for i in range(len(k)):
        if n%k[i]==0:
                a.append(k[i])

a.sort()

for i in range(len(a)):
        j=1
        while n%(a[i]**j)==0: 
                j=j+1
        b.append(j-1)

nod=1

for i in range(len(b)):
        nod=nod*(b[i]+1)

print('no.of divisors of {} = {}'.format(n,nod))

Я думаю, это то, что вы ищете. Я делаю именно то, что вы просили. Скопируйте и вставьте его в Блокнот. Сохраните как * .bat.Run.Enter Number. Умножьте процесс на 2, и это число делителей. Я сделал это специально, чтобы он быстрее определял делители:

Пожалуйста, обратите внимание, что переменная CMD поддерживает значения более 999999999

@echo off

modecon:cols=100 lines=100

:start
title Enter the Number to Determine 
cls
echo Determine a number as a product of 2 numbers
echo.
echo Ex1 : C = A * B
echo Ex2 : 8 = 4 * 2
echo.
echo Max Number length is 9
echo.
echo If there is only 1 proces done  it
echo means the number is a prime number
echo.
echo Prime numbers take time to determine
echo Number not prime are determined fast
echo.

set /p number=Enter Number : 
if %number% GTR 999999999 goto start

echo.
set proces=0
set mindet=0
set procent=0
set B=%Number%

:Determining

set /a mindet=%mindet%+1

if %mindet% GTR %B% goto Results

set /a solution=%number% %%% %mindet%

if %solution% NEQ 0 goto Determining
if %solution% EQU 0 set /a proces=%proces%+1

set /a B=%number% / %mindet%

set /a procent=%mindet%*100/%B%

if %procent% EQU 100 set procent=%procent:~0,3%
if %procent% LSS 100 set procent=%procent:~0,2%
if %procent% LSS 10 set procent=%procent:~0,1%

title Progress : %procent% %%%



if %solution% EQU 0 echo %proces%. %mindet% * %B% = %number%
goto Determining

:Results

title %proces% Results Found
echo.
@pause
goto start

я думаю, что этот будет удобен, а также точен

script.pyton

>>>factors=[ x for x in range (1,n+1) if n%x==0] print len(factors)

Попробуйте что-то вроде этого:

int divisors(int myNum) {
    int limit = myNum;
    int divisorCount = 0;
    if (x == 1) 
        return 1;
    for (int i = 1; i < limit; ++i) {
        if (myNum % i == 0) {
            limit = myNum / i;
            if (limit != i)
                divisorCount++;
            divisorCount++;
        }
    }
    return divisorCount;
}

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

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

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

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