Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1955 connectés 

  FORUM HardWare.fr
  Programmation

  Nombres prmier en C encore un truc SVP!???

 
 


Dernière réponse
Sujet : Nombres prmier en C encore un truc SVP!???
wpk

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é...


Votre réponse
Nom d'utilisateur    Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !
Le ton de votre message                        
                       
Votre réponse
[b][i][u][strike][spoiler][fixed][cpp][url][email][img][*]   
 
   [quote]
 
Options

 
Vous avez perdu votre mot de passe ?


Vue Rapide de la discussion
wpk

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é...

Kristoph 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
LeGreg

vendeeman a écrit a écrit :

svp, ça urge! :)  




 
pourquoi ton tp il finit a quelle heure?
 
LEGREG

Olivier51 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]
chrisbk pour afficher les 100 premier nb entier ?  
ben tu boucles !
vendeeman svp, ça urge! :)
vendeeman et pour afficher les 100 premiers entiers vous faites comment: merci pour votre aide CCCAAAAA MMMAAARRCCCHHHEEE!!!!
LeGreg Un peu optimise:

Code :
  1. int isPremier(int n)
  2. {
  3.    if (n%2==0) return 0;
  4.    int i = 3;
  5.    while (i*i<=n) {
  6.       if(n%i==0)
  7.              return 0;
  8.       i+=2;
  9.    }
  10.    return 1;
  11. }


 
A+
LEGREG

flo850 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
HelloWorld 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 :
  1. // soit un unsigned long int N à tester
  2.     int i, premier = 1;
  3.     long racine = sqrt(N);
  5.     for(i = 3; i <= racine; i += 2)
  6.     {
  7.         if((N % i) == 0)    // si reste division == 0
  8.         {
  9.             premier = 0;
  10.             break;
  11.         }
  12.     }


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

vendeeman 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]

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo

Copyright © 1997-2025 Groupe LDLC (Signaler un contenu illicite / Données personnelles)