Les Nombres Premiers
Fermé
abdelkarim_jb
Messages postés
25
Date d'inscription
samedi 27 novembre 2010
Statut
Membre
Dernière intervention
5 juin 2011
-
31 janv. 2011 à 20:55
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 2 févr. 2011 à 22:15
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 2 févr. 2011 à 22:15
A voir également:
- Les Nombres Premiers
- Code binaire des nombres - Guide
- Citez un des logiciels lui permettant de faire des calculs sur des tableaux de nombres (tableur). ✓ - Forum Logiciels
- Nombres faciles - Télécharger - Outils professionnels
- Supprimer les 0 devant un nombre excel ✓ - Forum Excel
- Algorithme maximum de 3 nombres ✓ - Forum Algorithmes / Méthodes
2 réponses
Doctor C
Messages postés
627
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
398
31 janv. 2011 à 21:15
31 janv. 2011 à 21:15
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.
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
2 févr. 2011 à 17:32
2 févr. 2011 à 17:32
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.
Zoul67
Messages postés
1959
Date d'inscription
lundi 3 mai 2010
Statut
Membre
Dernière intervention
30 janvier 2023
149
2 févr. 2011 à 20:40
2 févr. 2011 à 20:40
Bonsoir KX,
Joli. Pure curiosité : penses-tu qu'on puisse encore optimiser la complexité de l'algorithme en se basant sur le crible d'Eratosthène ? (car, par exemple, dans ta méthode on calcule n mod 15 alors que 15 n'est pas premier)
++
Joli. Pure curiosité : penses-tu qu'on puisse encore optimiser la complexité de l'algorithme en se basant sur le crible d'Eratosthène ? (car, par exemple, dans ta méthode on calcule n mod 15 alors que 15 n'est pas premier)
++
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
2 févr. 2011 à 22:15
2 févr. 2011 à 22:15
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.
