Algorithme pour trouver les facteurs d’un nombre donné. Méthode la plus courte?

Quelle pourrait être la logique la plus simple et la plus rapide pour trouver les facteurs d’un nombre donné? Existe-t-il un algorithme basé sur le même principe?

En fait, mon vrai problème est de trouver le non. de facteurs qui existent pour un nombre donné ..

Donc, tout algorithme, s’il vous plaît faites le moi savoir à ce sujet ..

Merci.

En fait, mon vrai problème est de trouver le non. de facteurs qui existent pour un nombre donné ..

Eh bien, c’est différent. Soit n le nombre donné.

Si n = p1^e1 * p2^e2 * ... * pk^ek , où chaque p est un nombre premier, le nombre de facteurs de n est (e1 + 1)*(e2 + 1)* ... *(ek + 1) . Plus à ce sujet ici .

Il suffit donc de trouver les puissances auxquelles chaque facteur premier apparaît. Par exemple:

 read given number in n initial_n = n num_factors = 1; for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number { power = 0; // suppose the power i appears at is 0 while (n % i == 0) // while we can divide n by i { n = n / i // divide it, thus ensuring we'll only check prime factors ++power // increase the power i appears at } num_factors = num_factors * (power + 1) // apply the formula } if (n > 1) // will happen for example for 14 = 2 * 7 { num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2 } 

Par exemple, prenez 18 . 18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6 . En effet, les 6 facteurs de 18 sont 1, 2, 3, 6, 9, 18 .

Voici un petit repère entre ma méthode et la méthode décrite et publiée par @Maciej. Son avantage est d’être plus facile à mettre en œuvre, alors que le mien a l’avantage d’être plus rapide si le changement consiste à ne parcourir que les nombres premiers, comme je l’ai fait pour ce test:

  class Program { static private List primes = new List(); private static void Sieve() { bool[] ok = new bool[2000]; for (int i = 2; i < 2000; ++i) // primes up to 2000 (only need up to sqrt of 1 000 000 actually) { if (!ok[i]) { primes.Add(i); for (int j = i; j < 2000; j += i) ok[j] = true; } } } private static int IVlad(int n) { int initial_n = n; int factors = 1; for (int i = 0; primes[i] * primes[i] <= n; ++i) { int power = 0; while (initial_n % primes[i] == 0) { initial_n /= primes[i]; ++power; } factors *= power + 1; } if (initial_n > 1) { factors *= 2; } return factors; } private static int Maciej(int n) { int factors = 1; int i = 2; for (; i * i < n; ++i) { if (n % i == 0) { ++factors; } } factors *= 2; if (i * i == n) { ++factors; } return factors; } static void Main() { Sieve(); Console.WriteLine("Testing equivalence..."); for (int i = 2; i < 1000000; ++i) { if (Maciej(i) != IVlad(i)) { Console.WriteLine("Failed!"); Environment.Exit(1); } } Console.WriteLine("Equivalence confirmed!"); Console.WriteLine("Timing IVlad..."); Stopwatch t = new Stopwatch(); t.Start(); for (int i = 2; i < 1000000; ++i) { IVlad(i); } Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds); Console.WriteLine("Timing Maciej..."); t.Reset(); t.Start(); for (int i = 2; i < 1000000; ++i) { Maciej(i); } Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds); } } 

Résultats sur ma machine:

Test d'équivalence ...
Equivalence confirmée!
Calendrier IVlad ...
Total millisecondes: 2448
Calendrier Maciej ...
Total millisecondes: 3951
Appuyez sur n'importe quelle touche pour continuer . . .

Il existe un grand nombre d’algorithmes disponibles – de la simple tentative d’essai aux algorithmes très sophistiqués pour les grands nombres. Jetez un coup d’œil à la factorisation des nombres entiers sur Wikipedia et choisissez-en une qui correspond à vos besoins.

Voici une implémentation C # courte mais inefficace qui recherche le nombre de facteurs premiers. Si vous avez besoin du nombre de facteurs (pas de facteurs premiers), vous devez enregistrer les facteurs premiers avec leur multiplicité et calculer ensuite le nombre de facteurs.

 var number = 3 * 3 * 5 * 7 * 11 * 11; var numberFactors = 0; var currentFactor = 2; while (number > 1) { if (number % currentFactor == 0) { number /= currentFactor; numberFactors++; } else { currentFactor++; } } 

Vous pouvez jeter un oeil à cet algorithme .

Voici un fruit de ma courte discussion avec | / | ad 🙂

 read given number in n int divisorsCount = 1; int i; for(i = 2; i * i < n; ++i) { if(n % i == 0) { ++divisorsCount; } } divisorsCount *= 2; if(i * i == n) { ++divisorsCount; } 

Attention, cette réponse n’est pas utile / rapide pour une valeur unique de n.

Méthode 1 :

Vous pouvez l’obtenir en O (polylog (n)) si vous gérez une table de correspondance (pour le premier facteur premier d’un nombre).

Si gcd (a, b) == 1, alors non. de facteurs de a * b = (nombre de facteurs de a) * (nombre de facteurs de b)

Par conséquent, pour un nombre donné a * b, si gcd (a, b)! = 1, nous pouvons avoir deux autres nombres p et q où p = a et q = b / gcd (a, b). Ainsi, gcd (p, q) == 1. Maintenant, nous pouvons trouver récursivement le nombre de facteurs pour p et q.

Quelques efforts seront nécessaires pour s’assurer que ni p ni q ne valent 1.

PS Cette méthode est également utile lorsque vous devez connaître le nombre de facteurs de tous les nombres de 1 à n. Ce serait un ordre de O (nlogn + O (table de consultation)).

Méthode 2 : (je n’ai pas la propriété pour cela.)

Si vous avez la recherche du premier facteur premier jusqu’à n, alors vous pouvez savoir que tous les facteurs premiers sont dans O (logn) et ainsi trouver le nombre de facteurs qui les composent.

PS Google “Factorisation dans la connexion” pour une meilleure explication.

L’algorithme d’Euclide devrait suffire.