Le plus grand facteur premier - Correction

Le plus grand facteur premier - Correction en Javascript

Problème :

Les facteurs premiers de 13195 sont 5, 7, 13 et 29.

Quel est le plus grand facteur premier d'un élément donné number? 

Solution :

Etape 1 : Vérifier qu'un nombre est premier

Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs. Ces deux diviseurs sont 1 et le nombre considéré.
- Wikipédia

En se basant sur cette définition, on peut vérifier qu'un nombre n est premier en s'assurant que tous les nombres entre 2 et n-1 ne divisent pas n. Le programme Javascipt correspondant est le suivant :

function estPremier(n){
  for(let i = 2; i <= n-1; i++){
    if(n%i==0) return false
  }
  return true
}

Oups ! Cet algorithme est trop lent..
En réalité, en incluant cet algorithme dans le programme finale, il le ferait cracher sur des grand nombre, comme 600851475143 par exemple.

Pour réduire le temps de calcul de notre algorithme, il nous faut fixer un seuil plus court que n-1.

Nous pouvons constater que le plus grand diviseur de n ne dépasse jamais n/2. De la même façon, il ne dépasse jamais la racine carrée de n. Ainsi, nous pouvons améliorer notre algorithme en prenant comme seuil la racine carrée de n.

function estPremier(n){
  const seuil = parseInt(Math.sqrt(n)) + 1 
  for(let i = 2; i < seuil; i++){
    if(n%i==0) return false
  }
  return true
}

Etape 2 : Chercher le plus grand facteur premier d'un nombre

Maintenant que nous savons comment vérifier qu'un nombre est premier, trouvons le plus grand facteur premier d'un nombre.

function plusGrandFacteur(n) {
  const seuil = parseInt(Math.sqrt(n)) + 1
  let max = n
  
  for(let i = 2; i < seuil; i++){
    if(n%i==0 && estPremier(i)) max = i
  }
  return max;
}

Important !

• Sur la ligne if(n%i==0 && estPremier(i)) max = i, il est impérentif de respecter l'ordre des conditions car estPremier(i) effectue beaucoup trop d'opérations. Il est donc préférable de vérifier d'abord que le nombre i est facteur avant de vérifier qu'il est facteur premier.
• La variable max a été initialisée avec la valeur n car les nombres premier sont leur propre plus grand facteur premier et n'aurons aucun diviseur dans la boucle for.

Le code final de cet algorithme est donc :

function estPremier(n){
  const seuil = parseInt(Math.sqrt(n)) + 1 
  for(let i = 2; i < seuil; i++){
    if(n%i==0) return false
  }
  return true
}
       
function plusGrandFacteur(n) {
  const seuil = parseInt(Math.sqrt(n)) + 1
  let max = n
  
  for(let i = 2; i < seuil; i++){
    if(n%i==0 && estPremier(i)) max = i
  }
  return max;
}

Pour aller plus loin !

Il existe un moyen plus rapide de résourdre ce problème. Cette autre méthode nécessite beaucoup plus d'espace mémoire. Vous pouvez vous amuser à la trouver et si possible à l'optimiser. Bonne chance !

Articles Similaires