Je cherche à faire un prog qui verifie si un nombre est premier: can youy help me please!
Merci d'avance!

[edtdd]--Message édité par vendeeman--[/edtdd]

Je viens de rendre un projet de cryptage RSA, donc basé sur les nombres premiers ...
Voici l'algo :
y'a pas 36 solutions, pour un nombre N, faut tester s'il est divisibles par tous les nombres de 2 à N-1 !
s'il n'y a aucun nombre, alors il est premier.
2 améliorations:
une évidente : on travaille uniquement avec les nombres impairs
 
for(i = 3; i < N; i += 2) ...
 
la deuxieme, faut le savoir:
 
au lieu de s'arreter à N-1, on s'arrete à SQRT(N) (sa racine carré)
ben ouai, c'est comme ça, si on a rien trouvé jusqu'à sa racine, on en trouvera pas après !
 
du coup:

 
j'ai fait vite, mais je crois que c'est ça !

int isPremier(int n)
{
   int i;
    for(i=2;i<n;i++)
          if(n%i==0)
             return 0;
    return 1;
}
 
voial la fonction bourrine, je te laisse l'ameliorer

Un peu optimise:

 
A+
LEGREG

et pour afficher les 100 premiers entiers vous faites comment: merci pour votre aide CCCAAAAA MMMAAARRCCCHHHEEE!!!!

svp, ça urge!

pour afficher les 100 premier nb entier ?  
ben tu boucles !

Pour l'optimisation, n'oublie pas la racine et de vérifier si ton nombre est divisible par 2 (donc tu commencera ta boucle de diviseur à 3, si il n'est pas divisible par 2).
 
Si tu recherches d'autres algo sur les nombres entiers va voir le doc que j'ai écrit pour le site http://www.codeur.org, voici l'adresse :
http://www.codeur.org/doc/doc.php?ID=12

[edtdd]--Message édité par Olivier51--[/edtdd]

vendeeman a écrit a écrit : svp, ça urge!

 
pourquoi ton tp il finit a quelle heure?
 
LEGREG

Vous devriez resortir vos bouqins sur la crypto. Quand on veut générer un nombre premier de grande taille, on ne se permet pas de tester la division par tout les nombres entiers impairs, du moins pas au début.
 
Il y a des techniques compliquées mais généralement en log n qui permettent de dire rapidement qu'un nombre n'est pas premier. La subtilitée c'est qu'elles ne permettent pas de dire qu'un nombre EST premier . Ca c'est des vieux souvenirs, je suis incapable maintenant de te donner le nom de ces algo . Si quelqu'un se rappelle, qu'il se manifeste svp
 
Une technique quand meme, tu généres un bon millier de nombres aléatoires et tu testes si le ppcm 2 à 2 de ces nombre et de ton candidat vaut 1. S'il vaut autre chose que 1 c'est que ton nombre n'est pas premier.
 
ppcm : Plus Petit Commun Multiple

Kristoph a écrit a écrit : Vous devriez resortir vos bouqins sur la crypto. Quand on veut générer un nombre premier de grande taille, on ne se permet pas de tester la division par tout les nombres entiers impairs, du moins pas au début.   Il y a des techniques compliquées mais généralement en log n qui permettent de dire rapidement qu'un nombre n'est pas premier. La subtilitée c'est qu'elles ne permettent pas de dire qu'un nombre EST premier . Ca c'est des vieux souvenirs, je suis incapable maintenant de te donner le nom de ces algo . Si quelqu'un se rappelle, qu'il se manifeste svp   Une technique quand meme, tu généres un bon millier de nombres aléatoires et tu testes si le ppcm 2 à 2 de ces nombre et de ton candidat vaut 1. S'il vaut autre chose que 1 c'est que ton nombre n'est pas premier.   ppcm : Plus Petit Commun Multiple

 
c'est meme plus complique que ca, il existe des tests de primalité (bcp bcp plus rapides que la methode triviale), pour les tres grands nombres qui fournissent une reponse  probabiliste pour savoir si oui ou non un nb est premier.
Cherche des infos autour du : test de fermat ou solovay-strassen ou miller-rabin (le dernier doit etre le meilleur des 3 si mes souvenirs sont bons). Ensuite, si tu veux des methodes sures, il me semble qu'il y a d'autres tests utilisant les courbes eliptiques mais c'est encore un peu plus compliqué...