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

performance algorithm pseudocode

143469 просмотра

27 ответа

7276 Репутация автора

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

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

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

Автор: sker Источник Размещён: 21.09.2008 05:44

Ответы (27)


1 плюс

17672 Репутация автора

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

Автор: SquareCog Размещён: 21.09.2008 05:53

0 плюса

600542 Репутация автора

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

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

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

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

Автор: Jonathan Leffler Размещён: 21.09.2008 05:59

78 плюса

5456 Репутация автора

Решение

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

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

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

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

Автор: Justin Bozonier Размещён: 21.09.2008 06:03

-1 плюса

1742 Репутация автора

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

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

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

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

Автор: SemiColon Размещён: 21.09.2008 06:16

5 плюса

675988 Репутация автора

Сито Аткина - это оптимизированная версия сита Эратосфена, которая дает все простые числа до заданного целого числа. Вы должны быть в состоянии 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
Автор: paxdiablo Размещён: 21.09.2008 06:36

47 плюса

8589 Репутация автора

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

Автор: user11318 Размещён: 21.09.2008 08:47

9 плюса

292308 Репутация автора

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

Автор: jfs Размещён: 21.09.2008 06:38

28 плюса

24631 Репутация автора

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

Автор: Tyler Размещён: 23.09.2008 01:53

10 плюса

594 Репутация автора

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

Автор: dongilmore Размещён: 04.11.2008 02:52

5 плюса

601 Репутация автора

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

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)
Автор: Michael Размещён: 18.07.2009 03:31

3 плюса

7616 Репутация автора

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

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

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

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

Автор: Loren Pechtel Размещён: 18.07.2009 04:11

5 плюса

51 Репутация автора

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

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

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

Автор: D. Williams Размещён: 02.02.2010 12:28

2 плюса

4280 Репутация автора

Делители делают что-то впечатляющее: они делятся полностью. Если вы хотите проверить число делителей для числа 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;
}

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

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

Автор: iGbanam Размещён: 30.12.2010 09:19

33 плюса

339 Репутация автора

@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;
}
Автор: Kendall Размещён: 23.03.2011 02:32

6 плюса

462 Репутация автора

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

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

Автор: هومن جاویدپور Размещён: 11.11.2011 02:59

1 плюс

11 Репутация автора

метод простых чисел здесь очень понятен. 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  .
Автор: abdelkarim Размещён: 09.01.2013 11:12

8 плюса

2571 Репутация автора

Вот прямой алгоритм 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  
Автор: Antony Thomas Размещён: 05.04.2013 04:32

1 плюс

87786 Репутация автора

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

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

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

  1. Проверьте, является ли число простым (быстрым)
  2. Если так, верните 2
  3. В противном случае, факторизовать число (медленно, если несколько больших простых факторов)
  4. Вычислить τ (n) из факторизации
Автор: Colonel Panic Размещён: 14.07.2013 12:15

1 плюс

1144 Репутация автора

Ниже приведена программа на 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++)
{
    ...
}
Автор: Lavish Kothari Размещён: 19.08.2014 01:35

1 плюс

752 Репутация автора

Вот функция, которую я написал. наихудшее время сложность 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;
}
Автор: Adilli Adil Размещён: 01.12.2014 01:02

3 плюса

41 Репутация автора

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

#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;
}
Автор: Эсмер Амрахлы Размещён: 01.12.2014 02:01

1 плюс

21 Репутация автора

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

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

    }
}
Автор: Malik Размещён: 02.12.2014 03:25

0 плюса

1 Репутация автора

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

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))
Автор: winsid96 Размещён: 29.11.2015 07:30

0 плюса

1 Репутация автора

Я думаю, это то, что вы ищете. Я делаю именно то, что вы просили. Скопируйте и вставьте его в Блокнот. Сохраните как * .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
Автор: dondon Размещён: 07.02.2016 09:24

1 плюс

314 Репутация автора

@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;
}
Автор: as2d3 Размещён: 11.11.2016 03:32

0 плюса

343 Репутация автора

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

script.pyton

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

Автор: Syed Hissaan Размещён: 23.01.2017 03:57

0 плюса

544 Репутация автора

Попробуйте что-нибудь в этом духе:

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;
}
Автор: Bryant Jackson Размещён: 23.01.2017 04:01
Вопросы из категории :
32x32