Obtenir toutes les nombres premiers dans une grande rangée au moins de 10 ms!

Soyez le premier à donner votre avis sur cette source.

Vue 7 441 fois - Téléchargée 264 fois

Description

salut
c'est comme vous avez compris du titre
c'est une implementation de l'algorithme sieve pour trouver les nombres premier.
détail dans le zip
merci pour votre visite!
:)

Source / Exemple :


#include<stdio.h>

    void sieve(int L,int U) {
      int i,j,d;
      d=U-L+1; 
      char flag[d];
      for (i=0;i<d;i++) flag[i]=1; /* par défaut tout est marqué comme premier */
      for (i=(L%2!=0);i<d;i+=2) flag[i]=0;
   /*on  élimine les multiples des nombres premiers de 3 jusqua sqrt(U) */
      for (i=3;i*i<=U;i+=2) {
         if (i>L && !flag[i-L]) 
            continue;
      /* On choisit le facteur qu'on va éliminer ses multiples */
         j=L/i*i; 
         if (j<L) j+=i;
         if (j==i) j+=i; /* il faut que j soit différent de i */
         j-=L; /* On décale les indices */
         for (;j<d;j+=i) flag[j]=0;
      }
      if (L<=1) flag[1-L]=0;
      if (L<=2) flag[2-L]=1;
      for (i=0;i<d;i++) 
         if (flag[i])
            printf("%d\n",L+i); 
   
   }
    int main(){
      int m,n;
      while(scanf("%d%d",&m,&n) == 2){
         sieve(m,n);
         printf("\n");
      } 
      return 0;
   }

Conclusion :


j'espère qu il sera utile pour vous!

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
77
Date d'inscription
mardi 27 juin 2006
Statut
Membre
Dernière intervention
12 août 2010

http://www.cppfrance.com/codes/RECHERCHE-NOMBRES-PREMIERS-CRIBLE-ERATOSTHENE_38335.aspx

Voila un exemple d'optimisation avec la mémoire. En plus avec les opérateurs basiques (&, |, <<, >>) on gagne beaucoup en vitesse.
Messages postés
77
Date d'inscription
mardi 27 juin 2006
Statut
Membre
Dernière intervention
12 août 2010

Pour bcc55, ça ne compile pas...
Messages postés
77
Date d'inscription
mardi 27 juin 2006
Statut
Membre
Dernière intervention
12 août 2010

"exactement Kirva!
son seul inconvénient c'est la grande mémoire!dieu merci qu'on est dans l'époque des 1Go de RAM!
a bientot.."
Justement pour la mémoire il y a une optimisation : on peut juste utiliser un bit par nombre impair, ça diminue par 16 l'espace mémoire requis. Comme ça on gagne 8 ans sur la technologie (loi de Moore). Pour la rapidité je ne sais pas si ça rend plus rapide ou moins (je dirais moins mais on ne sais pas car les opérateurs << et >> sont extremement rapides).
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Ben si, et c'est même très facile à prouver (ce qui ajoute à l'élégance de la démonstration ^^). Mais on parle ici de trouver tous les nombres premiers dans un intervalle fini, et ça, il y en a un nombre fini.
Messages postés
100
Date d'inscription
lundi 30 octobre 2006
Statut
Membre
Dernière intervention
14 avril 2009

il n'y a pas une infinite de nombres premiers ?
Afficher les 25 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.