NOMBRE PREMIER
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
26 sept. 2003 à 12:02
arkarod Messages postés 1 Date d'inscription lundi 19 avril 2004 Statut Membre Dernière intervention 20 juin 2004 - 20 juin 2004 à 01:10
arkarod Messages postés 1 Date d'inscription lundi 19 avril 2004 Statut Membre Dernière intervention 20 juin 2004 - 20 juin 2004 à 01:10
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/16683-nombre-premier
https://codes-sources.commentcamarche.net/source/16683-nombre-premier
20 juin 2004 à 01:10
En fait, un nombre premier est dit premier si et seulement il n'est divisible que par 1 et lui-même, ce qui fait que 1 est le premier nombre premier car il satisfait aux 2 conditions.
En ce qui concerne le fait d'aller jusqu'à la racine carrée entière, c'est dû au fait que la multiplication est commutative :
Par exemple, prenons 64, sa racine carrée est 8; tous les autres produits qui les composent sont formés d'un facteur inférieur à 8 et d'un facteur supérieur à 8 :
soit par exemple 4*16, si le test sur 4 à déjà été fait, celui sur 16 est inutile car 4*16 = 16*4.
Ce qui fait que si un diviseur entier est trouvé avant la racine carrée du nombre à tester, il y a forcémént un diviseur entier supérieur à la racine carrée et il n'est pas nécessaire d'en faire le test.
Pour finir, un moyen d'améliorer la méthode serait de tester uniquement les nombres 2, 3 et tous ceux qui répondent aux formules
((6*i)-1), ((6*i)+1) | avec i appartenant au domaine des entiers naturels car ce sont les seuls susceptibles d'êtres premiers, et tans qu'à faire, pour optimiser encore plus les tests, ces nombres pourraient êtres les seuls à devoir tester ceux qui suivent, pour éviter ainsi les tests redondants :
Par exemple, imaginons qu'un nombre soit testé avec le chiffre 3, il n'a plus besoin d'être testé avec le chiffre 9 pourtant, en ajoutant à chaque fois le chiffre 2 à 3, on obtient 5, 7, 9, 11, 13 avec le test sur 9
tandis qu'en prenant les formules précédantes avec i = 1, 2, 3, ..
on a 5 6*1-1, 7 6*1+1, 11 = 6*2-1, 13 = 6*2+1.
Il s'agit là de la méthode la plus optimisée qui donnant un résultat déterministe.
28 sept. 2003 à 14:40
Décomposer un nombre en un produit de facteurs premiers est au programme de math de 2° générale alors je pense que tu as du passer par là...
Bon je propose un algo qui compte le nombre de facteurs premiers d'un nombre et les stocke dans un tableau.
Il suffit de s'arrêter à la racine carée du nombre (sqrt(n), inclus dans <cmath>), je vais pas expliquer pourquoi, ça me semble quand même assez intuitif...
Si la valeur retournée est 1, le nombre est prenmier :
int NbFacteursPremiers(unsigned Nombre) {
unsigned n = Nombre ;
int c = 0 ; // compteur
int divTeste = 3, limitTest ;
while ( n % 2 == 0 && n != 1 ) {
FacteursPremiers[c] = 2 ;
c++ ;
n /= 2 ;
}
if ( n == 1 ) return c ;
while ( n > 1 ) {
limitTest = (int)(sqrt(n) + 1) ;
if ( divTeste >= limitTest ) {
FacteursPremiers[c]= n ;
c++ ;
return c ;
}
while ( n % divTeste == 0 ) {
FacteursPremiers[c] = divTeste ;
c++ ;
n /= divTeste ;
}
divTeste += 2 ;
} // while
return c ;
}
26 sept. 2003 à 19:44
PS:Je ne suis pas un matheux , je suis en Terminal Litteraire alors faut pas trop m'en demander.
26 sept. 2003 à 18:07
26 sept. 2003 à 18:02
26 sept. 2003 à 17:23
Mais il y a un probleme de programmation :
"while(diviseur<valeur-1)"
Le jour ou valeur-1 est (toujours) inferieur 2 il y aura un boucle infinie ! (bon au bout de 4 milliard d'iteration ce sera pire)
Donc il faut demander a l'utilisateur de renter un nombre STRICTEMEMT superieur a 1
Juste un petite amelioration ...
26 sept. 2003 à 17:19
26 sept. 2003 à 13:29
26 sept. 2003 à 12:11
if(diviseur==2)
{
diviseur++;
}
else
diviseur +=2;
mais je sais pas pourquoi ca marchait pas , je vais voir .
Quand tu dit reflechi jusqu'ou tester le diviseur , je pense que tu veut dire qu'il doit pas dépasser valeur/2 ?
Si c'est ca je vais changer.Merci pour tes conseils:)
26 sept. 2003 à 12:02
Autant etre clair c'est nul, a quoi sert de diviser par tous les nombres pairs ?
if(valeur & 1) a deja fait tous les nombres pairs.
Et reflechis jusqu'ou tester diviseur.
etc...