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

https://stackoverflow.com/questions/110344

02-07-2019
|

Вопрос

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

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

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

Решение

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

~~Вот немного Python для алгоритма~~ Смотри сюда и найдите «Тема:математика - нужен алгоритм делителей».Однако просто посчитайте количество элементов в списке, а не возвращайте их.

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

По сути, все сводится к тому, если ваш номер 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, гораздо быстрее, чем при проверке отдельных простых чисел.Если вы объедините этот метод исключения больших простых чисел с ситом, вы получите гораздо лучший метод факторизации, чем с использованием только сита.

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

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

@Яски

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

Пытаться:

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)

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

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

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 имеет дубликаты 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 и несколько полезных ссылок: А000005:d(n) (также называемый tau(n) или sigma_0(n)), количество делителей n.
реальный пример: факторизация целых чисел

Вот прямой алгоритм 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

ВСЕГО одна строка
Я очень осторожно подумал о вашем вопросе, и я попытался написать высокоэффективный и исполнительный кусок кода, чтобы распечатать все делители данного номера на экране, нам нужна только одна строка кода!(используйте опцию -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 Главная факторизация: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 τ(p**k) = k+1 (степени числа p).Таким образом, вы можете легко вычислить τ(n) путем его факторизации.

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

Проверить, является ли число простым (быстро)
Если да, верните 2
В противном случае, Факторизовать число (медленно, если несколько больших простых множителей)
Вычислите τ(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);

    }
}

@Кендалл

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

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. Введите число. Умножьте результат на 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

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

скрипт.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;
}

Вы можете предварительно вычислить простые числа до квадратного корня из максимально возможного N и вычислить показатель степени каждого простого множителя числа.Число делителей n (n = p1^a p2^b p3^c...) равно (a+1)(b+1)(c+1), потому что это то же самое, что и способ объединения простых чисел. числа этих множителей (и это будет считаться количеством делителей).Это очень быстро, если предварительно вычислить простые числа.

Более подробная информация об этом методе:

https://mathschallenge.net/library/number/number_of_divisors

https://www.math.upenn.edu/~deturck/m170/wk2/numdivisors.html

http://primes.utm.edu/glossary/xpage/tau.html

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

int divisors_count(const vector<int>& primes, int n)
{
    int divisors = 1;
    for (int i = 0; i < primes.size(); ++i) {
        int factor = primes[i];
        int factor_exponent = 0;
        while (n % factor == 0) {
            ++factor_exponent;
            n /= factor;
        }
        divisors *= (factor_exponent + 1);
    }
    if (n > 1) 
        return 2*divisors; // prime factor > sqrt(MAX_N)
    return divisors;
}

int main()
{
    const int MAX_N = 1e6;
    int max_factor = sqrt(MAX_N);

    vector<char> prime(max_factor + 1, true);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            for (int j = 3*i; j <= max_factor; j += 2*i) {
                prime[j] = false;
            }   
        }
    }

    vector<int> primes;
    primes.reserve(max_factor/2);
    primes.push_back(2);
    for (int i = 3; i <= max_factor; i += 2) {
        if (prime[i]) {
            primes.push_back(i);
        }
    }

    int n;
    while (cin >> n) {
        cout << divisors_count(primes, n) << endl;
    }
}

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow