Algorithme pour calculer le nombre de diviseurs d'un nombre donné

Question

Quel serait l'algorithme le plus optimal (en termes de performances) pour calculer le nombre de diviseurs d'un nombre donné?

Ce serait génial si vous pouviez fournir un pseudocode ou un lien vers un exemple.

EDIT: Toutes les réponses ont été très utiles, merci. Je suis en train de mettre en œuvre le Sieve of Atkin et ensuite je vais utiliser quelque chose de similaire à ce que Jonathan Leffler a indiqué. Le lien posté par Justin Bozonier contient de plus amples informations sur ce que je voulais.

Answer 1

Dmitriy est juste que vous voudrez le Crible d'Atkin pour générer le premier de la liste, mais je ne crois pas qu'il prend soin de l'ensemble de la question. Maintenant que vous avez une liste de nombres premiers, vous aurez besoin de savoir combien de ces nombres premiers agir comme un diviseur (et à quelle fréquence).

Voici quelques python pour l'algo Regardez ici et de la recherche pour "Objet: mathématiques - besoin diviseurs algorithme". Comptez simplement le nombre d'éléments dans la liste au lieu de les renvoyer.

Voici un Docteur en Mathématiques , qui explique ce que c'est exactement ce que vous devez faire mathématiquement.

Essentiellement, il se résume à si votre nombre n est:
n = a^x * b^y * c^z
(où a, b, et c sont n diviseurs premiers et x, y, et z sont le nombre de fois que le diviseur est répété) ensuite, le nombre total pour l'ensemble des diviseurs est:
(x + 1) * (y + 1) * (z + 1).

Edit: BTW, pour trouver a,b,c,etc vous aurez envie de faire ce qui équivaut à un gourmand algo si je suis à la compréhension de ce correctement. Commencez avec votre plus grand diviseur premier et de le multiplier par lui-même jusqu'à ce qu'une multiplication à dépasser le nombre n de. Puis passer à la prochaine moins important et la fois le précédent premier ^ nombre de fois qu'il a été multipliée par l'actuel premier et le multiplie par le premier jusqu'à la prochaine dépassera n... etc. Garder une trace du nombre de fois que vous le multipliez les diviseurs ensemble et d'appliquer ces nombres dans la formule ci-dessus.

Pas sûr à 100% sur mon algo description, mais si que n'est-il pas que c'est quelque chose de similaire .

Answer 2

Il y a beaucoup plus de techniques d'affacturage que le crible d'Atkin. Par exemple, supposons que nous voulons facteur 5893. Sa racine est 76.76... nous allons Maintenant tenter d'écrire 5893 comme un produit de places. (77*77 - 5893) = 36 6 au carré, de sorte 5893 = 77*77 - 6*6 = (77 + 6)(77-6) = 83*71. Si cela n'avait pas fonctionné, nous aurions regardé si 78*78 - 5893 est un carré parfait. Et ainsi de suite. Avec cette technique, vous pouvez rapidement tester les facteurs de près de la racine carrée de n beaucoup plus rapide que par des essais individuels de nombres premiers. Si vous combinez cette technique pour écarter les grands nombres premiers avec un tamis, vous aurez une bien meilleure affacturage méthode qu'avec le tamis seul.

Et ce est juste une seule d'un grand nombre de techniques qui ont été développées. C'est assez simple. Il vous faudra beaucoup de temps pour apprendre, disons, assez de théorie pour comprendre la prise en compte des techniques basées sur les courbes elliptiques. (Je sais qu'ils existent. Je ne les comprends pas.)

Par conséquent, sauf si vous travaillez avec de petits nombres entiers, je ne voudrais pas essayer de résoudre le problème moi-même. Au lieu de cela je vais essayer de trouver un moyen d'utiliser quelque chose comme le PARI de la bibliothèque qui a déjà une très bonne solution mise en œuvre. Avec qui je peux facteur aléatoire de 40 chiffres comme 124321342332143213122323434312213424231341 dans environ .05 secondes. (Sa factorisation, dans le cas où vous êtes-vous demandé, est 29*439*1321*157907*284749*33843676813*4857795469949. Je suis assez confiant qu'elle n'ai pas de chiffre à l'aide du crible d'Atkin...)

Answer 3

@Yasky

Votre fonction diviseurs a un bug en ce sens qu'elle ne fonctionne pas correctement pour les carrés parfaits.

Essayer:

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

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

    return numberOfDivisors;
}
 

Answer 4

Je ne suis pas d'accord sur le fait que le tamis d'Atkin est la voie à suivre, car cela pourrait prendre plus de temps à vérifier chaque nombre dans [1, n] que la primalité que de réduire le nombre par divisions.

Voici un code qui, bien que légèrement plus piraté, est généralement beaucoup plus rapide:

 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 Cela fonctionne du code python pour résoudre ce problème.

Answer 5

Cette question est intéressante, est d'autant plus difficile qu'il n'y paraît, et il n'a pas été répondu. La question peut être pris en compte dans 2 questions très différentes.

1 étant donné N, trouver la liste L de N facteurs premiers

2 compte tenu de L, calculer le nombre de combinaisons uniques

Toutes les réponses que je vois à ce jour reportez-vous à #1 et de ne pas mentionner qu'il n'est pas docile pour un nombre énorme. De taille modérée N, même en 64 bits, il est facile, pour d'énormes N, de l'affacturage problème peut prendre "pour toujours". Chiffrement à clé publique en dépend.

Question #2 a besoin de plus de discussions. Si L ne contient que des numéros uniques, c'est un simple calcul à l'aide de la combinaison de la formule de choisir k objets parmi n objets. En fait, vous avez besoin de faire la somme des résultats de l'application de la formule en faisant varier k de 1 à sizeof(L). Cependant, L contiennent généralement plusieurs occurrences multiples des nombres premiers. Par exemple, L = {2,2,2,3,3,5} est la factorisation de N = 360. Maintenant ce problème est assez difficile!

En retraitant #2, compte tenu de la collection de C contenant k éléments, tels que le point a a un "doublons, et le point b a b" doublons, etc. combien de combinaisons uniques de 1 à k-1 les articles sont là? Par exemple, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} chacun doit se produire une fois et une fois seulement si L = {2,2,2,3,3,5}. Chacun de ces sous-collection est un unique diviseur de N en multipliant les éléments de la sous-collection.