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

Question

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

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

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

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

метод простых чисел здесь очень понятен. 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  .

Answer 6

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

Answer 7

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

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

    }
}

Answer 8

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

Answer 9

Вот функция, которую я написал. наихудшее время сложность 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;
}

Answer 10

Ниже приведена программа на 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++)
{
    ...
}