CRIBLE D'ERATOSTHENE

Commentaire de yvkoe le 10/10/2007 16:58:05

Bonjour,
très classe ,c'est important, la technique est primordiale mais après il faut sortir des chantiers battus.
Et là c'est le cas
Bravo!

Commentaire de ltb69 le 16/10/2007 12:49:22

Trois petites remarques :
- Tu déclare la variable du compteur (i) en début de méthode. Il est plus clair de la mettre directement dans le for => en plus çà évite les effets de bord si tu veux réutiliser la variable
- Tu fais des tas de calcul, pour ne utiliser le tableau dans sa totalité (les "-2" qui trainent) => pourquoi ne pas plutôt perdre les deux premières cases (0 et 1). le code serait plus clair.
- Tu utilise -1 dans les conditions d'arrêt des for ( par ex i<=tableau_premiers.length-1). Par habitude, j'utilise plutôt : i<tableau_premiers.length. La condition d'arrêt est calculée à chaque boucle.


L'inconvénient de ta méthodes est qu'elle est de complexité n² => Pour tous les chiffres, tu reparcours tout les chiffres suivant (même si tu ne fais pas d'action) ==> somme ==> n²/2
Il vaudrait mieux du code en complexite n (lineaire) du style :
    for (i = 2; i <= borne_sup; i++)
    {
      if (tableau_premiers[i])
      { // bypass les nbres non 1ers
        mult = 2;
        toto = i * mult;
        while (toto <= borne_sup)
        {
          tableau_premiers[(int) toto] = false;
          mult++;
          toto = i * mult;
        }
      }
    }

Pour info, on obtient un temps équivalent (8-9s), pour les nombres entre 2 à 10000, pour 50 appels à ta méthode ou 15000 appels de l'autre version.

Quant à lequel de tes deux algo est le plus rapide ... je dirais qu'ils se valent en performance pur, si ce n'est qu'ici tu fait l'impasse sur pas mal de calcul. Tu passes, en gros, de 10000² à 1229² (soit de 100000000 à 1510441 soit un gros facteur 60). En améliorant la complexité, tu as en plus un facteur 300.
Comme me disais un prof : Il vaut mieux améliorer la complexité de l'algo plutôt que l'algo lui même.

Commentaire de chabacha le 19/10/2007 15:23:19

Bah !
Bonjour à tous

merci Yvkoe pour la note et merci ltb69 et LEFAUVE42 pour les remarques.
C vrai, mais si on veut aller plus loin dans notre optimisation ... il suffit de combiner plusieurs théorèmes.
Par exemple, le plus facile et immediat, serait d'appliquer le théoreme (conséquence du théoreme de Bertrand) suivant :
un nombre naturel n qui n'est divisible par aucun nombre premier p <= racine(n) est automatiquement lui-même premier.
Il est inutile, donc, de prolonger les recherches au-delà de racine de n. Il suffit d'atteindre le dernier nbre premier (p) telque p<=racine(borne superieure choisie) pour sortir de la boucle ...(ça tombe bien : par defaut le tableau est à true, donc à la sortie selon cette condition on aura nos nbres premiers jusqu'à la borne_sup).
exemple : borne_sup =100 donc il suffit de terminer le crible au nombre 7 !
Sauf que l'affichage devra se faire en dehors de la boucle ...
voici le code modifié :
class Eratosthene {
/*Recherche des nombres tels qu'ils ne sont divisibles
que par eux même (ou 1!)*/
public static void main (String args[]) {
    int i,j,borne_sup=35100,nbr_int_premier=0;
    boolean []tableau_premiers = new boolean [borne_sup-1];
    
    for (i=0;i<=tableau_premiers.length-1;i++)
    {
        tableau_premiers[i]=true;
    }
    // le chiffre 2 est premier "par defaut", d'ailleurs, tous au debut.
    for (i=2;i*i<=borne_sup;i++) // i<=racine(borne_sup)
    {
     if (tableau_premiers[i-2]==true){ // bypass les nbres non 1ers
        j=i+1;
        while (j<=borne_sup)
        {
        if ((j%i)==0) tableau_premiers[j-2]=false;
        j++;
        }
       // nbr_int_premier++;
      // if (nbr_int_premier%13!=0) System.out.print(i+" ");
      // else System.out.println(i+" ");
     }
    }
for (i=0;i<=tableau_premiers.length-1;i++)
{
    if (tableau_premiers[i]==true)
    {
    nbr_int_premier++;
       if (nbr_int_premier%13!=0) System.out.print(i+2+" ");
        else System.out.println(i+2+" ");
    }
}
    System.out.println("");
    System.out.println("Nomre de nbr premiers : "+nbr_int_premier+" entre "+2+" et "+borne_sup);
}
}