Les Nombres Premiers
abdelkarim_jb
Messages postés
25
Date d'inscription
Statut
Membre
Dernière intervention
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
Bonjour,
Est Ce Que quelqu'un pourrai m'aidez a resoudre ce probleme : " ecrivez un sous programme si un entier plus grand que 1 est premiers ou non "
Merci :)
Est Ce Que quelqu'un pourrai m'aidez a resoudre ce probleme : " ecrivez un sous programme si un entier plus grand que 1 est premiers ou non "
Merci :)
A voir également:
- Les Nombres Premiers
- Code binaire des nombres - Guide
- Nombres faciles - Télécharger - Outils professionnels
- Trouver un numéro avec les 6 premiers chiffres - Forum Freebox
- Citez un des logiciels lui permettant de faire des calculs sur des tableaux de nombres (tableur). - Forum Excel
- Dans ce fichier, réalisez le graphique xy (nuage de points ou dispersion), avec les x en abscisse. dans le graphique, les points dessinent un nombre. lequel ? - Forum Bureautique
2 réponses
Un nombre premier est un nombre qui ne se divise que par 1 et par lui-même.
Donc, étant un nombre n, tu pourrais faire une boucle de 1+1 à n -1 et si aucune division n/i ne donne zéro, n est premier.
Ex:
Bon, je suis malade présentement et mon cerveau n'est pas tout à fait en pleine forme mais je croix que ce code fonctionne. Ou du moins la logique.
Il manque des trucs du genre (si n>1) etc. mais ce sont des détails que tu peux corriger.
Donc, étant un nombre n, tu pourrais faire une boucle de 1+1 à n -1 et si aucune division n/i ne donne zéro, n est premier.
Ex:
int n = 13;
Bool estPremier = vrai;
Pour (i = 1+1 ; i < n ; i++)
Si n modulo i == 0 Alors
estPremier = faux;
break;
Bon, je suis malade présentement et mon cerveau n'est pas tout à fait en pleine forme mais je croix que ce code fonctionne. Ou du moins la logique.
Il manque des trucs du genre (si n>1) etc. mais ce sont des détails que tu peux corriger.
Remarque
On peut gagner la moitié du nombre de calculs en ne considérant que les nombres impairs, les nombres pairs n'étant pas premiers (excepté 2).
Et pour enlever encore plus de calculs inutiles, il faut s'arrêter à la racine carrée de n.
En effet il ne peut exister de diviseur de n supérieur à sqrt(n) excepté n lui même.
Du coup si n est premier on le saura après 2+sqrt(n)/2 calculs (nombre de tests if).
Avant on aurait fait n-2 calculs en testant toutes les valeurs de 2 jusqu'à n-1.
Exemple
n = 2^31-1 (c'est le plus grand integer en Pascal, et il est premier)
Avant on aurait fait 2 147 483 645 calculs pour dire que ce nombre est premier, alors qu'ici je n'en ai besoin que de 23 171 pour arriver à la même conclusion.
On peut gagner la moitié du nombre de calculs en ne considérant que les nombres impairs, les nombres pairs n'étant pas premiers (excepté 2).
Et pour enlever encore plus de calculs inutiles, il faut s'arrêter à la racine carrée de n.
En effet il ne peut exister de diviseur de n supérieur à sqrt(n) excepté n lui même.
Du coup si n est premier on le saura après 2+sqrt(n)/2 calculs (nombre de tests if).
Avant on aurait fait n-2 calculs en testant toutes les valeurs de 2 jusqu'à n-1.
Exemple
n = 2^31-1 (c'est le plus grand integer en Pascal, et il est premier)
Avant on aurait fait 2 147 483 645 calculs pour dire que ce nombre est premier, alors qu'ici je n'en ai besoin que de 23 171 pour arriver à la même conclusion.
function estPremier(n:integer):boolean;
var i,r:integer;
begin
if (n < 2) // 0 et 1 ne sont pas premiers
then exit(false);
if (n mod 2 = 0) // 2 est le seul nombre pair premier
then exit(n=2);
i:=3;
r:=trunc(sqrt(real(n))); // r = racine carrée de n
while (i <= r) do
if (n mod i = 0) // si i divise n
then exit(false) // n n'est pas premier : n = i*(n/i)
else i:=i+2; // on considère le nombre impair suivant
exit(true);
end;
VAR i:integer;
BEGIN
for i:=0 to 100 do
if estPremier(i)
then writeln(i);
readln;
END.
Effectivement, dès qu'on commence à mettre un peu de connaissance pour guider notre recherche c'est forcément plus efficace, car le calcul n mod i = 0 est bien plus lourd que de regarder dans une grille si on n'a pas déjà calculé sa valeur (surtout pour les très grands nombres).
Cependant il ne faut pas oublier que la crible utilise activement la mémoire et pour les très grands nombres cette consommation peut rapidement poser problème alors que la grille est fortement creuse (tous les deux, tous les trois, tous les cinq... ça revient très souvent).
C'est pour cela qu'il existe des algorithmes plus efficaces, le crible d'Atkin par exemple.
Cependant il ne faut pas oublier que la crible utilise activement la mémoire et pour les très grands nombres cette consommation peut rapidement poser problème alors que la grille est fortement creuse (tous les deux, tous les trois, tous les cinq... ça revient très souvent).
C'est pour cela qu'il existe des algorithmes plus efficaces, le crible d'Atkin par exemple.