Algorithme pour trouver les facteurs d'un nombre donné .. Méthode la plus courte?
Ce qui pourrait être le plus simple et efficace du temps de logique pour trouver les facteurs d'un Nombre donné.
Est-il un algorithme qui existent, basées sur le même.
En fait, mon vrai problème est de trouver le no. de facteurs qui existent pour un Nombre donné..
Donc de l'algorithme, s'il vous plaît laissez-moi savoir sur ce..
Grâce.
source d'informationauteur AGeek
Vous devez vous connecter pour publier un commentaire.
Bien, ce qui est différent. Laissez
n
être le nombre donné.Si
n = p1^e1 * p2^e2 * ... * pk^ek
où chaquep
est un nombre premier, alors le nombre de facteurs den
est(e1 + 1)*(e2 + 1)* ... *(ek + 1)
. En savoir plus sur cette ici.Par conséquent, il suffit de trouver des compétences à laquelle chaque facteur apparaît. Par exemple:
Par exemple, prendre
18
.18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6
. En effet, la6
facteurs de18
sont1, 2, 3, 6, 9, 18
.Voici un petit benchmark entre ma méthode et la méthode décrite et posté par @Maciej. Sa a l'avantage d'être plus facile à mettre en œuvre, alors que la mienne a l'avantage d'être plus rapide si le changement à seulement itérer sur les nombres premiers, comme je l'ai fait pour ce test:
Résultats sur ma machine:
Il y a un grand nombre d'algorithmes disponibles à partir de simples procès devision de très algorithmes sophistiqués pour les grands nombres. Jetez un oeil à La Factorisation D'Entiers sur Wikipédia et d'en choisir un qui convient à vos besoins.
Voici une courte, mais inefficace, C# de mise en œuvre qui trouve le nombre de facteurs premiers. Si vous avez besoin le nombre de facteurs (pas de facteurs premiers), vous devez stocker les facteurs premiers avec leur multiplicité et de calculer le nombre de facteurs à la suite.
Vous pouvez prendre un coup d'oeil à cet algorithme.
Ici est un fruit de ma courte discussion avec |/|ad 🙂
Attention, cette réponse n'est pas utile et rapide pour une seule valeur de n.
Méthode 1:
Vous pouvez l'obtenir en O(polylog(n)) si vous maintenez une look-up table (pour le premier facteur d'un nombre).
Si pgcd(a,b) == 1, alors
pas de. des facteurs de a*b = (no. des facteurs) * (no. des facteurs de b)
Donc, pour un nombre donné a*b, si pgcd(a,b) != 1 ensuite, on peut avoir deux autres nombres p et q, où p = et q = b/pgcd(a,b). Donc, pgcd(p,q) == 1. Maintenant, nous pouvons de manière récursive trouver le nombre de facteurs de p et q.
Il ne prendra qu'une petite quantité d'efforts déployés pour s'assurer que ni p ni q est 1.
P. S. Cette méthode est également utile lorsque vous avez besoin de connaître le nombre de facteurs de tous les nombres de 1 à n. Il serait de l'ordre de O(nlogn + O(look-up table)).
Méthode 2: (je n'ai pas de propriété).
Si vous avez le look-up pour le premier facteur jusqu'à n, alors vous pouvez savoir c'est tous les facteurs premiers en O(logn) et trouver ainsi le nombre de facteurs d'eux.
P. S. Google 'la Factorisation dans logn' pour une meilleure explication.
D'euclide l'Algorithme devrait suffire.