Algoritmo para calcular o número de divisores de um determinado número

StackOverflow https://stackoverflow.com/questions/110344

Pergunta

Qual seria o algoritmo mais ideal (em termos de performance) para calcular o número de divisores de um dado número?

Vai ser ótimo se você pudesse fornecer pseudocódigo ou um link para alguns exemplos.

EDIT: Todas as respostas têm sido muito úteis, obrigado. Estou implementando o Crivo de Atkin e então eu vou usar algo semelhante ao que Jonathan Leffler indicado. O link postado por Justin Bozonier tem mais informações sobre o que eu queria.

Foi útil?

Solução

Dmitriy é certo que você vai querer o Crivo de Atkin para gerar a lista nobre, mas eu não acredito que cuida de toda a questão. Agora que você tem uma lista de números primos você precisa ver quantos desses números primos agir como um divisor (e quantas vezes).

Eis alguns python para a algo Olhe aqui e procure por "Assunto: matemática - divisores necessidade Algorithm". Basta contar o número de itens na lista em vez de devolvê-los no entanto.

Aqui está uma Dr. Math que explica exatamente o que é que você precisa fazer matematicamente.

Essencialmente, resume-se se o seu número n é:
n = a^x * b^y * c^z
(Onde a, b, e c são n é divisores e x prima, y, e z são o número de vezes que é repetido divisor) em seguida, a contagem total de todos os divisores é:
(x + 1) * (y + 1) * (z + 1).

Editar: BTW, para encontrar a, b, c, etc você vai querer fazer o que equivale a um algo ganancioso se eu estou entendendo isso corretamente. Comece com o seu maior divisor primo e multiplicá-lo por si mesmo enquanto se aguarda uma multiplicação excederia o número n. Em seguida, passar para o próximo fator menor e os tempos do primeiro anterior ^ número de vezes que ele foi multiplicado pelo atual primeiro e continuam se multiplicando pelo primeiro até o próximo irá exceder n ... etc. Mantenha o controle do número de vezes que você multiplicar o divisores em conjunto e aplicar esses números na fórmula acima.

Não 100% de certeza sobre a minha descrição algo, mas se não é isso que é algo similar.

Outras dicas

Há uma muito mais técnicas para factoring do que a peneira de Atkin. Por exemplo, suponha que queremos fator de 5893. Bem sua sqrt é 76,76 ... Agora vamos tentar escrever 5893 como um produto de quadrados. Bem (77 * 77-5893) = 36, o qual é 6 quadrado, de modo 5893 = 77 * 77-6 * 6 = (77 + 6) (77-6) = 83 * 71. Se isso não tivesse trabalhado teríamos analisaram se 78 * 78-5893 era um quadrado perfeito. E assim por diante. Com esta técnica, você pode testar rapidamente para fatores de perto a raiz quadrada de n muito mais rápido do que testando primos individuais. Se você combinar esta técnica para descartar grandes números primos com a peneira, você terá um método muito melhor factoring do que apenas com a peneira.

E este é apenas um de um grande número de técnicas que têm sido desenvolvidos. Esta é uma pergunta bastante simples. Levaria muito tempo para aprender, dizem, teoria dos números o suficiente para entender as técnicas de factoring com base em curvas elípticas. (Eu sei que eles existem. Eu não entendo eles.)

Portanto, a menos que você está lidando com números inteiros pequenos, eu não iria tentar resolver o problema sozinho. Em vez disso eu tentar encontrar uma maneira de usar algo como o PARI biblioteca que já uma solução altamente eficiente implementada. Com que eu posso levar um número de 40 dígitos aleatórios como 124321342332143213122323434312213424231341 em cerca de .05 segundos. (Sua fatoração, no caso de você se perguntou, é 29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949. Estou bastante confiante de que ele não descobrir isso usando a peneira de Atkin ...)

@Yasky

A sua função divisor tem um bug em que ele não funciona corretamente para quadrados perfeitos.

Tente: 

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

Eu discordo que a peneira de Atkin é o caminho a percorrer, porque ele poderia facilmente levar mais tempo para verificar cada número em [1, n] para primality do que seria para reduzir o número de divisões.

Aqui está um código que, embora ligeiramente hackier, é geralmente muito mais rápido: 

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 que está trabalhando código python para resolver este problema.

Esta questão interessante é muito mais difícil do que parece, e não foi respondida. A questão pode ser tido em conta em 2 questões muito diferentes.

1 dado N, encontrar a lista L de primordial factores de N

2 dado L, número de calcular de combinações únicas

Todas as respostas que eu vejo até agora referem-se a # 1 e deixar de mencionar que não é tratável para números enormes. Para tamanho moderado N, mesmo números de 64 bits, é fácil; para enorme N, o problema factoring pode levar "para sempre". criptografia de chave pública depende disso.

Pergunta # 2 necessidades mais discussão. Se L contém apenas números únicos, é um cálculo simples usando a fórmula de combinação para a escolha de k objetos a partir de n itens. Na verdade, é necessário somar os resultados da aplicação da fórmula ao mesmo tempo variando de 1 a k sizeof (L). No entanto, L geralmente contêm várias ocorrências de vários primos. Por exemplo, L = {2,2,2,3,3,5} é a fatoração de N = 360. Agora este problema é muito difícil!

Reafirmando # 2, determinada coleção C contendo itens K, de tal forma que um item tem uma 'duplicatas, e no item b tem b' duplicatas, etc. quantas combinações únicas de 1 a K-1 itens estão lá? Por exemplo, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} deve ocorrer cada vez e só uma vez que se L = {2,2 , 2,3,3,5}. Cada um desses sub-coleção exclusiva é um divisor única de N multiplicando os itens da sub-coleção.

Uma resposta à sua pergunta depende muito do tamanho do inteiro. Métodos para pequenas quantidades, por exemplo menos de 100 bits, e para os números de ~ 1000 de bits (tal como usado em criptografia) são completamente diferentes.

Aqui está uma frente O (sqrt (n)) algoritmo em linha reta. Eu usei isto para resolver projeto Euler 

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

apenas uma linha
Tenho pensado muito carefuly sobre sua pergunta e eu tentei escrever uma peça altamente eficiente e performance de código Para imprimir todos os divisores de um dado número na tela precisamos de apenas uma linha de código! (Use a opção -std = c99 ao compilar via 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

para encontrar números de divisores você pode usar a seguinte função muito, muito rápido (trabalho corretamente para todos número inteiro exceto 1 e 2) 

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return counter;
}

ou se você tratar determinado número como um divisor (trabalho corretamente para todos número inteiro exceto 1 e 2) 

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

NOTA: dois acima funções funciona corretamente para todos número inteiro positivo, exceto número 1 e 2 por isso é funcional para todos os números que são maiores do que 2 mas se você precisa para cobrir 1 e 2, você pode usar uma das seguintes funções (um pouco mais lento) 

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

ou 

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

o pequeno é bonito:)

A peneira de Atkin é uma versão otimizada da peneira de Eratóstenes, que dá a todos os números primos até um determinado número inteiro. Você deve ser capaz de google isso para mais detalhes.

Depois de ter essa lista, é uma simples questão de dividir o seu número por cada privilegiada para ver se é um divisor exato (ou seja, o restante é zero).

Os passos básicos cálculo dos divisores para um número (n) são [isto é pseudocódigo convertido a partir do código real, então eu espero que eu não introduziram erros]: 

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

Você pode tentar este. É um pouco hackish, mas é razoavelmente rápido. 

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

Depois de ter o primeiro-factorização, há uma maneira de encontrar o número de divisores. Adicionar um para cada um dos expoentes em cada fator individual e multiplicar o expoentes juntos.

Por exemplo: 36 Prime Fatoração: 2 ^ 2 * 3 ^ 2 Divisores: 1, 2, 3, 4, 6, 9, 12, 18, 36 Número de divisores: 9

Adicionar um para cada expoente 2 ^ 3 * 3 ^ 3 expoentes multiplicam: 3 * 3 = 9

Antes de se comprometer a uma solução consideram que a abordagem Sieve pode não ser uma boa resposta no caso típico.

Um tempo atrás havia uma questão primordial e eu fiz um teste do tempo - para inteiros de 32 bits, pelo menos, que determinam se era nobre foi mais lento do que força bruta. Há dois fatores que vão em:

1) Enquanto um ser humano leva um tempo para fazer uma divisão que eles são muito rápidos no computador -. Semelhante ao custo de procurar a resposta

2) Se você não tem uma mesa primordial que você pode fazer um loop que é executado inteiramente no cache L1. Isso torna mais rápido.

Esta é uma solução eficiente: 

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

Divisores fazer algo espetacular: eles dividem completamente. Se você quiser verificar o número de divisores de um número, n, é evidente que é redundante para abranger todo o espectro, 1...n. Eu não fiz nenhuma pesquisa em profundidade para isso, mas eu resolvi problema Projeto de Euler 12 em números triangulares . Minha solução para os maior do que 500 divisores ran teste para 309504 microssegundos (~ 0.3s). Eu escrevi essa função divisor para a solução. 

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

Para cada algoritmo, há um ponto fraco. Eu pensei que este era fraco contra números primos. Mas desde que os números triangulares não são imprimir, ele serviu seu objetivo na perfeição. Do meu profiling, eu acho que fez muito bem.

Boas festas.

Você quer o Crivo de Atkin, descritos aqui: http://en.wikipedia.org/wiki / Sieve_of_Atkin

o método número primo é muito claro aqui. P [] é uma lista de números primos menos do que ou igual a 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  .

Número de livros de teoria chamar a função tau-contando divisor. O primeiro fato interessante é que é multiplicativo, ou seja. t (ab) = t (a) t (b), quando a e b não têm factor comum. . (Prova: cada par de divisores de um e b dá um divisor distinta de ab)

Agora, nota que, para p um primo, t (p ** k) = k + 1 (os poderes p). Assim, você pode facilmente t compute (n) a partir de sua factorisation.

No entanto fatoração de grandes números podem ser lento (a segurança da RSA crytopraphy depende do produto de dois números primos grandes sendo difícil factorise). Isso sugere esse otimizado algoritmo

  1. Teste se o número é primo (rápido)
  2. Se assim for, o retorno 2
  3. Caso contrário, factorise o número (lento se vários grandes fatores primos)
  4. Compute t (n) do factorisation

O seguinte é um programa C para encontrar o número de divisores de um determinado número.

A complexidade do algoritmo acima é O (sqrt (n)).

Este algoritmo irá funcionar corretamente para o número que são quadrado perfeito, bem como os números que não são quadrado perfeito.

Note que o UPPERLIMIT do loop é definida para a raiz quadrada do número de ter o algoritmo mais eficiente.

Note que armazenar o UPPERLIMIT em uma variável separada também economiza o tempo, você não deve chamar a função sqrt na seção condição do loop for, isso também poupa o seu tempo computacional. 

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

Em vez do acima para o laço você também pode usar o seguinte circuito que é ainda mais eficiente, pois isso elimina a necessidade de encontrar a raiz quadrada do número. 

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

Aqui é uma função que eu escrevi. É o pior complexidade de tempo é O (sqrt (n)), o melhor tempo do outro lado é O (log (n)). Dá-lhe todos os divisores primos, juntamente com o número de sua ocorrência. 

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

Esta é a forma mais básica de computar os divissors número: 

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

Eu testei seu código e fez algumas melhorias, agora é ainda mais rápido. Eu também testado com @ ???? ???????? código, este também é mais rápido do que o seu código. 

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

Não é este apenas uma questão de factoring o número - determinar todos os fatores do número? Você pode então decidir se você precisa de todas as combinações de um ou mais fatores.

Assim, um algoritmo possível seria: 

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

É então até você para combinar os fatores para determinar o resto da resposta.

Isso é algo que eu vim acima com base em Justin resposta. Ele pode exigir alguma otimização. 

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

Eu acho que isso é o que você está procurando for.I faz exatamente o que você pediu. Copie e cole-o em Notepad.Save como * .bat.Run.Enter Number.Multiply o processo pelo 2 e isso é o número de divisors.I fez isso de propósito para que o que determinam os divisores mais rápido:

Pls notar que um CMD valores de apoio varriable cativas ao longo 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

eu acho que este vai ser útil, bem como precisa

script.pyton

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

Tente algo ao longo destas linhas: 

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

Você pode precompute números primos até a raiz sqaure do máximo possível N e calcular o expoente de cada fator primordial de um número. O número de divisores de n (n = p1 ^ a p2 ^ b P3 ^ c ...) é (a + 1) (b + 1) (c + 1) porque é o mesmo que contar a maneira de combinar o nobre números de esta factores (e isto irá contar o número de divisores). Isto é muito rápido se você precompute os números primos

Informações mais detalhadas sobre este método:

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

Eu não sei o método mais eficiente, mas eu faria o seguinte:

  • Criar uma tabela de números primos para encontrar todos os números primos menores ou iguais à raiz quadrada do número (Pessoalmente, eu uso o Crivo de Atkin)
  • Contagem todos os primos menor ou igual à raiz quadrada do número e multiplicar por dois. Se a raiz quadrada do número é um inteiro, em seguida, subtrair um do variável de contagem.

deve funcionar \ o /

Se precisar, eu posso código alguma coisa amanhã em C para demonstrar.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top