Comment trouver tous les facteurs d’un nombre naturel en C++, Python et JavaScript

Hibou Gourou

Un facteur est un nombre qui divise exactement un nombre donné ; c'est-à-dire qu'il divise le nombre sans laisser de reste. Trouver les facteurs d'un nombre à l'aide de la programmation peut vous aider à consolider vos concepts de boucles, d'instructions conditionnelles et d'opérateurs modulo.

Dans cet article, vous apprendrez à trouver tous les facteurs d'un nombre naturel en utilisant C++, Python et JavaScript.

Énoncé du problème

On vous donne un nombre naturel num , vous devez trouver et imprimer tous les facteurs distincts de num .

Exemple 1 : Soit num = 60.

Les facteurs de 60 sont : 1 2 3 4 5 6 10 12 15 20 30 60

Ainsi, la sortie est 1 2 3 4 5 6 10 12 15 20 30 60.

Exemple 2 : Soit num = 100.

Les facteurs de 100 sont : 1 2 4 5 10 20 25 50 100

La sortie est donc 1 2 4 5 10 20 25 50 100.

Exemple 3 : Soit num = 85.

Les facteurs de 85 sont : 1 5 17 85

La sortie est donc de 1 5 17 85.

Approche de base pour résoudre le problème

Vous pouvez trouver tous les facteurs distincts d'un nombre en suivant l'approche ci-dessous :

  1. Itérer tous les nombres de 1 à num .
  2. Si le nombre divise parfaitement num , imprimez le nombre.

En utilisant cette approche, la complexité temporelle de la solution serait O(n) et l'espace auxiliaire requis serait O(1).

Programme C++ pour trouver les facteurs d'un nombre

Ci-dessous le programme C++ pour trouver tous les facteurs d'un nombre :

 // C++ program to find all factors of a natural number
 #include <iostream>
 using namespace std;
 void findFactors(int num)
 {
 for(int i=1; i<=num; i++)
 {
 if(num%i == 0)
 {
 cout << i << " ";
 }
 }
 cout << endl;
 }
 int main()
 {
 int num1 = 60;
 cout << "Factors of " << num1 << " are: " << endl;
 findFactors(num1);
 int num2 = 100;
 cout << "Factors of " << num2 << " are: " << endl;
 findFactors(num2);
 int num3 = 85;
 cout << "Factors of " << num3 << " are: " << endl;
 findFactors(num3);
 int num4 = 66;
 cout << "Factors of " << num4 << " are: " << endl;
 findFactors(num4);
 int num5 = 71;
 cout << "Factors of " << num5 << " are: " << endl;
 findFactors(num5);
 return 0;
 }

Production:

 Factors of 60 are:
 1 2 3 4 5 6 10 12 15 20 30 60
 Factors of 100 are:
 1 2 4 5 10 20 25 50 100
 Factors of 85 are:
 1 5 17 85
 Factors of 66 are:
 1 2 3 6 11 22 33 66
 Factors of 71 are:
 1 71

Programme Python pour trouver les facteurs d'un nombre

Ci-dessous le programme Python pour trouver tous les facteurs d'un nombre :

 # Python program to find all factors of a natural number
 def findFactors(num):
 for i in range(1,num+1):
 if (num%i==0):
 print(i, end=" ")
 print()
 num1 = 60
 print("Factors of", num1, "are:")
 findFactors(num1)
 num2 = 100
 print("Factors of", num2, "are:")
 findFactors(num2)
 num3 = 85
 print("Factors of", num3, "are:")
 findFactors(num3)
 num4 = 66
 print("Factors of", num4, "are:")
 findFactors(num4)
 num5 = 71
 print("Factors of", num5, "are:")
 findFactors(num5)

Production:

 Factors of 60 are:
 1 2 3 4 5 6 10 12 15 20 30 60
 Factors of 100 are:
 1 2 4 5 10 20 25 50 100
 Factors of 85 are:
 1 5 17 85
 Factors of 66 are:
 1 2 3 6 11 22 33 66
 Factors of 71 are:
 1 71

Connexes : Comment trouver le LCM et le GCD de deux nombres dans plusieurs langues

Programme JavaScript pour trouver les facteurs d'un nombre

Ci-dessous se trouve le programme JavaScript pour trouver tous les facteurs d'un nombre :

 // JavaScript program to find all factors of a natural number
 function findFactors(num) {
 for(let i=1; i<=num; i++) {
 if(num%i == 0) {
 document.write(i + " ");
 }
 }
 document.write("<br>");
 }

 let num1 = 60;
 document.write("Factors of " + num1 + " are: " + "<br>");
 findFactors(num1);
 let num2 = 100;
 document.write("Factors of " + num2 + " are: " + "<br>");
 findFactors(num2);
 let num3 = 85;
 document.write("Factors of " + num3 + " are: " + "<br>");
 findFactors(num3);
 let num4 = 66;
 document.write("Factors of " + num4 + " are: " + "<br>");
 findFactors(num4);
 let num5 = 71;
 document.write("Factors of " + num5 + " are: " + "<br>");
 findFactors(num5);

Production:

 Factors of 60 are:
 1 2 3 4 5 6 10 12 15 20 30 60
 Factors of 100 are:
 1 2 4 5 10 20 25 50 100
 Factors of 85 are:
 1 5 17 85
 Factors of 66 are:
 1 2 3 6 11 22 33 66
 Factors of 71 are:
 1 71

Connexes : Introduction à l'algorithme de tri par fusion

Approche optimisée pour résoudre le problème

Si vous regardez les facteurs d'un nombre, ils apparaissent par paires. Par exemple, si num = 64, les facteurs de 64 seraient : (1, 64), (2, 32), (4, 16) et (8, 8). Vous pouvez utiliser ce fait pour optimiser votre solution.

Cependant, dans le cas de deux facteurs égaux, vous ne devez imprimer le facteur qu'une seule fois. Comme dans l'exemple ci-dessus, (8, 8) sont deux facteurs égaux. Vous n'avez donc besoin de les imprimer qu'une seule fois.

Ainsi, vous pouvez utiliser l'approche optimisée suivante pour trouver tous les facteurs distincts d'un nombre :

  1. Itérer tous les nombres de 1 à la racine carrée de num .
  2. Si le nombre divise parfaitement num , cela signifie que le nombre est un facteur de num .
  3. Vérifiez maintenant si le deuxième facteur ( num /1er facteur) est égal au premier facteur.
  4. Si les deux facteurs sont égaux, imprimez le facteur une fois.
  5. Si les deux facteurs sont inégaux, imprimez les deux facteurs.

En utilisant cette approche, la complexité temporelle de la solution est O(sqrt(n)) et l'espace auxiliaire requis est O(1).

Programme C++ utilisant une approche optimisée pour trouver les facteurs d'un nombre

Ci-dessous le programme C++ pour trouver tous les facteurs d'un nombre :

 // C++ program to find all factors of a natural number
 #include <bits/stdc++.h>
 using namespace std;
 void findFactors(int num)
 {
 for(int i=1; i<=sqrt(num); i++)
 {
 if(num%i == 0)
 {
 if(num/i == i)
 {
 cout << i << " ";
 }
 else
 {
 cout << i << " " << num/i << " ";
 }
 }
 }
 cout << endl;
 }
 int main()
 {
 int num1 = 60;
 cout << "Factors of " << num1 << " are: " << endl;
 findFactors(num1);
 int num2 = 100;
 cout << "Factors of " << num2 << " are: " << endl;
 findFactors(num2);
 int num3 = 85;
 cout << "Factors of " << num3 << " are: " << endl;
 findFactors(num3);
 int num4 = 66;
 cout << "Factors of " << num4 << " are: " << endl;
 findFactors(num4);
 int num5 = 71;
 cout << "Factors of " << num5 << " are: " << endl;
 findFactors(num5);
 return 0;
 }

Production:

 Factors of 60 are:
 1 60 2 30 3 20 4 15 5 12 6 10
 Factors of 100 are:
 1 100 2 50 4 25 5 20 10
 Factors of 85 are:
 1 85 5 17
 Factors of 66 are:
 1 66 2 33 3 22 6 11
 Factors of 71 are:
 1 71

Connexe : Comment inverser une chaîne en C++, Python et JavaScript

Programme Python utilisant une approche optimisée pour trouver les facteurs d'un nombre

Ci-dessous le programme Python pour trouver tous les facteurs d'un nombre :

 # Python program to find all factors of a natural number
 import math
 def findFactors(num):
 i = 1
 while i <= math.sqrt(num):
 if (num%i==0):
 if (num/i == i):
 print(i, end=" ")
 else:
 print(i, num//i, end=" ")
 i = i + 1
 print()
 num1 = 60
 print("Factors of", num1, "are:")
 findFactors(num1)
 num2 = 100
 print("Factors of", num2, "are:")
 findFactors(num2)
 num3 = 85
 print("Factors of", num3, "are:")
 findFactors(num3)
 num4 = 66
 print("Factors of", num4, "are:")
 findFactors(num4)
 num5 = 71
 print("Factors of", num5, "are:")
 findFactors(num5)

Production:

 Factors of 60 are:
 1 60 2 30 3 20 4 15 5 12 6 10
 Factors of 100 are:
 1 100 2 50 4 25 5 20 10
 Factors of 85 are:
 1 85 5 17
 Factors of 66 are:
 1 66 2 33 3 22 6 11
 Factors of 71 are:
 1 71

Programme JavaScript utilisant une approche optimisée pour trouver les facteurs d'un nombre

Ci-dessous se trouve le programme JavaScript pour trouver tous les facteurs d'un nombre :

 // JavaScript program to find all factors of a natural number
 function findFactors(num) {
 for(let i=1; i<=Math.sqrt(num); i++) {
 if(num%i == 0) {
 if (parseInt(num/i, 10) == i)
 {
 document.write(i + " ");
 } else {
 document.write(i + " " + parseInt(num/i, 10) + " ");
 }
 }
 }
 document.write("<br>");
 }

 let num1 = 60;
 document.write("Factors of " + num1 + " are: " + "<br>");
 findFactors(num1);
 let num2 = 100;
 document.write("Factors of " + num2 + " are: " + "<br>");
 findFactors(num2);
 let num3 = 85;
 document.write("Factors of " + num3 + " are: " + "<br>");
 findFactors(num3);
 let num4 = 66;
 document.write("Factors of " + num4 + " are: " + "<br>");
 findFactors(num4);
 let num5 = 71;
 document.write("Factors of " + num5 + " are: " + "<br>");
 findFactors(num5);

Production:

 Factors of 60 are:
 1 60 2 30 3 20 4 15 5 12 6 10
 Factors of 100 are:
 1 100 2 50 4 25 5 20 10
 Factors of 85 are:
 1 85 5 17
 Factors of 66 are:
 1 66 2 33 3 22 6 11
 Factors of 71 are:
 1 71

Comprendre les principes de base de la programmation

En tant que programmeur, il est très important de comprendre les principes de base de la programmation tels que KISS (Keep It Simple, Stupid), DRY (Ne vous répétez pas), Responsabilité unique, YAGNI (Vous n'en aurez pas besoin), Ouvert/Fermé, Composition sur héritage, etc.

Suivre les principes de base de la programmation fera de vous un meilleur programmeur.