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

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.

    Dmisortingy a raison de dire que vous voudrez que le Sieve of Atkin génère la liste principale, mais je ne crois pas que cela prenne en compte l’ensemble du problème. Maintenant que vous avez une liste de nombres premiers, vous devrez voir combien de ces nombres premiers agissent comme un diviseur (et à quelle fréquence).

    Voici un python pour l’algo Regardez ici et recherchez “Sujet: maths – algorithme des diviseurs”. Il suffit de compter le nombre d’éléments dans la liste au lieu de les renvoyer.

    Voici un Dr. Math qui explique ce que vous devez faire mathématiquement.

    Essentiellement, cela revient à si votre numéro n est:
    n = a^x * b^y * c^z
    (où a, b et c sont les premiers diviseurs de n et x, y et z sont le nombre de fois que le diviseur est répété) alors le nombre total pour tous les diviseurs est:
    (x + 1) * (y + 1) * (z + 1) .

    Edit: BTW, pour trouver a, b, c, etc., vous voudrez faire ce qui revient à un algo gourmand si je comprends bien. Commencez avec votre plus grand diviseur premier et multipliez-le par lui-même jusqu’à ce qu’une multiplication supplémentaire dépasse le nombre n. Puis déplacez-vous vers le facteur le plus bas et multipliez le nombre de fois où il a été multiplié par le nombre premier et continuez à multiplier par le nombre maximal jusqu’à ce que le nombre supérieur dépasse n … etc. diviseurs ensemble et appliquer ces chiffres dans la formule ci-dessus.

    Pas sûr à 100% de ma description d’algo, mais si ce n’est pas le cas, c’est quelque chose de similaire.

    Il y a beaucoup plus de techniques de factorisation que le tamis d’Atkin. Par exemple, supposons que nous voulions factoriser 5893. Et bien, son nombre est de 76,76 … Nous allons maintenant essayer d’écrire 5893 comme un produit de carrés. Eh bien (77 * 77 – 5893) = 36 qui est 6 au carré, donc 5893 = 77 * 77 – 6 * 6 = (77 + 6) (77-6) = 83 * 71. Si cela n’avait pas fonctionné, nous aurions examiné si 78 * 78 – 5893 était un carré parfait. Etc. Avec cette technique, vous pouvez tester rapidement des facteurs proches de la racine carrée de n, en testant des nombres premiers individuels. Si vous combinez cette technique pour éliminer les grands nombres premiers avec un tamis, vous aurez une méthode d’affacturage beaucoup plus efficace qu’avec le tamis seul.

    Et ce n’est là qu’une des nombreuses techniques développées. C’est assez simple. Il vous faudrait beaucoup de temps pour apprendre, par exemple, suffisamment de théorie des nombres pour comprendre les techniques de factorisation basées sur les courbes elliptiques. (Je sais qu’ils existent. Je ne les comprends pas.)

    Par conséquent, sauf si vous avez affaire à de petits nombres entiers, je n’essaierais pas de résoudre ce problème moi-même. Au lieu de cela, j’essaierais de trouver un moyen d’utiliser quelque chose comme la bibliothèque PARI qui dispose déjà d’une solution très efficace. Avec cela je peux prendre en compte un nombre aléatoire de 40 chiffres comme 124321342332143213122323434312213424231341 dans environ 0,05 secondes. (Sa factorisation, au cas où vous vous le demanderiez, est de 29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949. Je suis persuadé qu’elle n’a pas compris cela en utilisant le tamis d’Atkin …)

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

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

    Cette question intéressante est beaucoup plus difficile qu’elle n’y paraît, et aucune réponse n’a été trouvée. La question peut être intégrée dans deux questions très différentes.

    1 donné N, trouve la liste des facteurs premiers L de N

    2 donné L, calculer le nombre de combinaisons uniques

    Toutes les réponses que je vois jusqu’ici se rapportent au numéro 1 et, à défaut de le mentionner, ne sont pas faciles à gérer pour des nombres énormes. Pour les tailles N, même les nombres 64 bits, c’est facile; pour N énorme, le problème d’affacturage peut prendre “pour toujours”. Le cryptage par clé publique en dépend.

    La question n ° 2 nécessite plus de discussion. Si L ne contient que des nombres uniques, il s’agit d’un calcul simple utilisant la formule de combinaison pour choisir k objects parmi n éléments. En fait, vous devez additionner les résultats en appliquant la formule en faisant varier k de 1 à sizeof (L). Cependant, L contiendra généralement plusieurs occurrences de plusieurs 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 rappelant le numéro 2, étant donné la collection C contenant k éléments, de telle sorte que l’élément a des doublons, et l’élément b des doublons, etc., combien de combinaisons uniques de 1 à k-1 existe-t-il? Par exemple, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} doivent apparaître une fois et une seule fois si L = {2,2 , 2,3,3,5}. Chaque sous-collection unique est un diviseur unique de N en multipliant les éléments de la sous-collection.

    Une réponse à votre question dépend beaucoup de la taille de l’entier. Les méthodes pour les petits nombres, par exemple moins de 100 bits, et pour les nombres de 1000 bits (tels que ceux utilisés en cryptographie) sont complètement différentes.

    • aperçu général: http://en.wikipedia.org/wiki/Divisor_function

    • valeurs pour n petit et quelques références utiles: AOOOOO5: d (n) (aussi appelé tau (n) ou sigma_0 (n)), le nombre de diviseurs de n.

    • exemple du monde réel: factorisation des nombres entiers

    Voici un algorithme simple O (sqrt (n)). Je l’ai utilisé pour résoudre le projet 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 

    JUST une ligne
    J’ai réfléchi très attentivement à votre question et j’ai essayé d’écrire un morceau de code très efficace et performant. Pour imprimer tous les diviseurs d’un nombre donné à l’écran, nous n’avons besoin que d’une seule ligne de code! (utilisez l’option -std = c99 lors de la compilation 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 

    pour trouver le nombre de diviseurs, vous pouvez utiliser la fonction très rapide suivante (fonctionne correctement pour tous les nombres entiers sauf 1 et 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 si vous traitez un nombre donné comme un diviseur (travaillez correctement pour tous les nombres entiers sauf 1 et 2)

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

    NOTE: deux fonctions ci-dessus fonctionnent correctement pour tous les nombres entiers positifs, à l'exception des nombres 1 et 2; elles sont donc fonctionnelles pour tous les nombres supérieurs à 2 mais si vous devez couvrir 1 et 2, vous pouvez utiliser l'une des fonctions suivantes (un peu Ralentissez)

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

    petit est beau 🙂

    Le tamis d’Atkin est une version optimisée du tamis d’Eratosthenes qui donne tous les nombres premiers jusqu’à un entier donné. Vous devriez être capable de google ceci pour plus de détails.

    Une fois que vous avez cette liste, il est facile de diviser votre nombre par chaque nombre premier pour voir si c’est un diviseur exact (c.-à-d. Que le rest est zéro).

    Les étapes de base pour calculer les diviseurs d’un nombre (n) sont [ceci est un pseudo-code converti à partir du code réel, alors j’espère que je n’ai pas introduit d’erreurs]:

     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 

    Vous pourriez essayer celui-ci. C’est un peu piraté, mais c’est assez rapide.

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

    Une fois que vous avez la factorisation en nombres premiers, il existe un moyen de trouver le nombre de diviseurs. Ajoutez un à chacun des exposants sur chaque facteur individuel, puis multipliez les exposants ensemble.

    Par exemple: 36 Factorisation initiale: 2 ^ 2 * 3 ^ 2 Diviseurs: 1, 2, 3, 4, 6, 9, 12, 18, 36 Nombre de diviseurs: 9

    Ajouter un à chaque exposant 2 ^ 3 * 3 ^ 3 Multiplier les exposants: 3 * 3 = 9

    Avant de vous engager dans une solution, considérez que l’approche Sieve pourrait ne pas être une bonne réponse dans le cas typique.

    Il y a quelque temps, il y avait une question primordiale et j’ai fait un test de temps – pour les entiers de 32 bits déterminant au moins si c’était premier était plus lent que la force brute. Deux facteurs interviennent:

    1) Tandis qu’un être humain prend un certain temps pour faire une division, il est très rapide sur l’ordinateur, ce qui est similaire au coût de la recherche.

    2) Si vous ne possédez pas de table principale, vous pouvez créer une boucle qui s’exécute entièrement dans le cache L1. Cela le rend plus rapide.

    Ceci est une solution efficace:

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

    Les diviseurs font quelque chose de spectaculaire: ils se divisent complètement. Si vous voulez vérifier le nombre de diviseurs pour un nombre, n , il est clairement redondant de couvrir tout le spectre, 1...n . Je n’ai pas fait de recherches approfondies pour cela, mais j’ai résolu le problème 12 du projet Euler sur les nombres sortingangulars . Ma solution pour le test de plus de 500 diviseurs a duré 309504 microsecondes (~ 0,3s). J’ai écrit cette fonction de diviseur pour la solution.

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

    Pour chaque algorithme, il y a un point faible. Je pensais que c'était faible par rapport aux nombres premiers. Mais comme les nombres sortingangulars ne sont pas imprimés, ils ont parfaitement fonctionné. De mon profilage, je pense que cela s'est très bien passé.

    Joyeuses fêtes.

    Vous voulez le Sieve of Atkin, décrit ici: http://en.wikipedia.org/wiki/Sieve_of_Atkin

    la méthode des nombres premiers est très claire ici. P [] est une liste de nombre premier inférieur ou égal à 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 . 

    Les manuels de théorie des nombres appellent la fonction de comptage de diviseur tau. Le premier fait intéressant est que c’est multiplicatif, c’est à dire. τ (ab) = τ (a) τ (b), quand a et b n’ont pas de facteur commun. (Preuve: chaque paire de diviseurs de a et b donne un diviseur distinct de ab).

    Notons maintenant que pour pa prime, τ (p ** k) = k + 1 (les puissances de p). Ainsi, vous pouvez facilement calculer τ (n) à partir de sa factorisation.

    Cependant, la factorisation des grands nombres peut être lente (la sécurité de la crypopraphie RSA dépend du produit de deux grands nombres premiers difficiles à factoriser). Cela suggère cet algorithme optimisé

    1. Teste si le nombre est premier (rapide)
    2. Si oui, retournez 2
    3. Sinon, factoriser le nombre (lent si plusieurs grands facteurs premiers)
    4. Calculer τ (n) à partir de la factorisation

    Ce qui suit est un programme en C pour trouver le nombre de diviseurs d’un nombre donné.

    La complexité de l’algorithme ci-dessus est O (sqrt (n)).

    Cet algorithme fonctionnera correctement pour le nombre de carrés parfaits ainsi que pour les nombres qui ne sont pas des carrés parfaits.

    Notez que la limite supérieure de la boucle est définie sur la racine carrée du nombre pour que l’algorithme soit le plus efficace.

    Notez que le stockage de la limite supérieure dans une variable distincte fait également gagner du temps, vous ne devez pas appeler la fonction sqrt dans la section condition de la boucle for, cela économise également votre temps de calcul.

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

    Au lieu de la boucle ci-dessus, vous pouvez également utiliser la boucle suivante, qui est encore plus efficace, car cela évite de rechercher la racine carrée du numéro.

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

    Voici une fonction que j’ai écrite. sa pire complexité est O (sqrt (n)), le meilleur temps par contre est O (log (n)). Il vous donne tous les diviseurs principaux avec le nombre de ses occurrences.

     public static List divisors(n) { ArrayList 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; } 

    C’est le moyen le plus fondamental de calculer les diviseurs de nombres:

     class PrintDivisors { public static void main(Ssortingng 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

    J’ai testé votre code et apporté quelques améliorations, maintenant il est encore plus rapide. J’ai aussi testé avec le code @ هومن جاویدپور, c’est aussi plus rapide que son code.

     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’est-ce pas juste une question de prise en compte du nombre – déterminant tous les facteurs du nombre? Vous pouvez ensuite décider si vous avez besoin de toutes les combinaisons d’un ou de plusieurs facteurs.

    Ainsi, un algorithme possible serait:

     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 

    Il vous appartient alors de combiner les facteurs pour déterminer le rest de la réponse.

    C’est quelque chose que j’ai trouvé sur la base de la réponse de Justin. Cela peut nécessiter une optimisation.

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

    Je pense que c’est ce que vous recherchez. Je fais exactement ce que vous avez demandé. Copiez-le et collez-le dans Notepad.Save en tant que * .bat.Run.Enter Number.Multipliez le processus par 2 et le nombre de diviseurs.Je l’ai fait express afin qu’il détermine plus rapidement les diviseurs:

    Veuillez noter qu’une variable CMD ne supporte pas les valeurs sur 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 

    Je suppose que celui-ci sera pratique et précis

    script.pyton

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

    Essayez quelque chose dans ce sens:

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

    Vous pouvez pré-calculer les nombres premiers jusqu’à la racine sqaure du N maximum possible et calculer l’exposant de chaque facteur premier d’un nombre. Le nombre de diviseurs de n (n = p1 ^ un p2 ^ b p3 ^ c …) est (a + 1) (b + 1) (c + 1) car c’est la même chose que compter la manière de combiner le premier nombre de ces facteurs (et cela comptera le nombre de diviseurs). C’est très rapide si vous pré-calculez les nombres premiers

    Informations plus détaillées sur cette méthode:

    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  #include  #include  #include  using namespace std; int divisors_count(const vector& 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 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 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; } } 

    Je ne connais pas la méthode la plus efficace, mais je ferais ce qui suit:

    • Créez une table de nombres premiers pour trouver tous les nombres premiers inférieurs ou égaux à la racine carrée du nombre (Personnellement, j’utiliserais le tamis d’Atkin)
    • Comptez tous les nombres premiers inférieurs ou égaux à la racine carrée du nombre et multipliez cela par deux. Si la racine carrée du nombre est un entier, soustrayez-en un de la variable count.

    Devrait fonctionner \ o /

    Si vous en avez besoin, je peux coder quelque chose demain en C pour démontrer.