Nombres prmier en C encore un truc SVP!??? - Programmation
Marsh Posté le 04-02-2002 à 13:18:44
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:
Code :
|
j'ai fait vite, mais je crois que c'est ça !
Marsh Posté le 04-02-2002 à 13:19:21
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
Marsh Posté le 04-02-2002 à 13:24:17
Un peu optimise:
Code :
|
A+
LEGREG
Marsh Posté le 04-02-2002 à 13:57:16
et pour afficher les 100 premiers entiers vous faites comment: merci pour votre aide CCCAAAAA MMMAAARRCCCHHHEEE!!!!
Marsh Posté le 04-02-2002 à 15:16:13
pour afficher les 100 premier nb entier ?
ben tu boucles !
Marsh Posté le 04-02-2002 à 15:30:21
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]
Marsh Posté le 04-02-2002 à 15:32:13
vendeeman a écrit a écrit : svp, ça urge! |
pourquoi ton tp il finit a quelle heure?
LEGREG
Marsh Posté le 04-02-2002 à 15:42:10
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
Marsh Posté le 05-02-2002 à 00:42:39
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é...
Marsh Posté le 04-02-2002 à 13:07:03
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]