begin process at 2010 02 09 16:49:21
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Maths et Algorithmes

 > NOMBRES PREMIERS PAR LE CRIBLE D'ERATOSTHÈNE VERSION OPTIMISÉE

NOMBRES PREMIERS PAR LE CRIBLE D'ERATOSTHÈNE VERSION OPTIMISÉE


 Information sur la source

Note :
Aucune note
Catégorie :Maths et Algorithmes Classé sous :crible, nombres premiers, tableau, ensemble, Eratosthène Niveau :Débutant Date de création :02/02/2009 Date de mise à jour :05/02/2009 14:07:33 Vu :3 879

Auteur : Virtuoooose

Ecrire un message privé
Commentaire sur cette source (10)
Ajouter un commentaire et/ou une note

 Description

Pour trouver tous les nombres premiers de 2 à Max, le principe est le suivant :
1. Construire l'ensemble de tous les entiers de 2 à Max
2. Extraire et afficher le plus petit élément de l'ensemble car c'est un nombre premier
3. Enlever de l'ensemble tous les multiples de ce nombre premier
4. Revenir à l'étape 2 jusqu'à ce que l'ensemble soit vide.

Source

  • public class Main {
  • public static void main(String[] args) {
  • afficherNombresPremiers(100);
  • }
  • public static void afficherNombresPremiers(int n) {
  • System.out.println("Les nombre premier de 0 à " + n + " sont :");
  • boolean[] tab = new boolean[n + 1];
  • //initialisation du tableau
  • for (int i = 0; i <= n; i++) {
  • tab[i] = true;
  • }
  • //on retire les nombres impaires
  • for (int i = 4; i <= n; i += 2) {
  • tab[i] = false;
  • }
  • // on sait déja que 2 est premier :
  • // car tab[2] = true;
  • System.out.println("2");
  • for (int i = 3; i <= n; i += 2) {
  • // on utilise des pas de 2, car tout les nombres pairs ne sont pas premiers.
  • if (tab[i] == true) {
  • System.out.println(i);
  • for (int j = i; j <= n; j += i) {
  • tab[j] = false;
  • }
  • }
  • }
  • }
  • }
public class Main {

    public static void main(String[] args) {
        afficherNombresPremiers(100);
    }

    public static void afficherNombresPremiers(int n) {
        System.out.println("Les nombre premier de 0 à " + n + " sont :");
        boolean[] tab = new boolean[n + 1];
        //initialisation du tableau
        for (int i = 0; i <= n; i++) {
            tab[i] = true;
        }
        //on retire les nombres impaires
        for (int i = 4; i <= n; i += 2) {
            tab[i] = false;
        }
        // on sait déja que 2 est premier :
        // car tab[2] = true;
        System.out.println("2");

        for (int i = 3; i <= n; i += 2) {
            // on utilise des pas de 2, car tout les nombres pairs ne sont pas premiers.
            if (tab[i] == true) {
                System.out.println(i);
                for (int j = i; j <= n; j += i) {
                    tab[j] = false;
                }
            }
        }
    }
}



 Historique

03 février 2009 12:43:46 :
modification grâce à coucou747. La condition étant inutile.
04 février 2009 18:18:41 :
Optimisation du code
04 février 2009 20:51:21 :
up
04 février 2009 20:52:25 :
voilou
05 février 2009 14:05:57 :
:)
05 février 2009 14:07:33 :
code final

 Sources de la même categorie

Source avec Zip CLASSE MATRICE par frankladen11
Source avec Zip Source avec une capture RÉSOLUTION D'ÉQUATION GRÂCE AU CALCUL DES DÉTERMINANTS par frankladen11
Source avec Zip TYPE DE DONNÉES ABSTRAIT GRAPHE par smutsonberg
Source avec Zip Source avec une capture SIMPLEXE ET DUAL par MrRenaud
Source avec Zip ALGORITHME DE BELLMAN, CALCUL DES TEMPS AU PLUS TÔT ET RECHE... par michaelcourcy2005

 Sources en rapport avec celle ci

CRIBLE D'ERATOSTHENE par chabacha
Source avec Zip GESTION D’UNE BANQUE DE RENSEIGNEMENTS SUR LES ESPIONS ('UTI... par anthony65
Source avec Zip CRIBLE QUADRATIQUE (FACTORISATION) par Pole4
Source avec Zip GESTION DE TABLEAUX AVEC TAILLE ET NOMBRE DE DIMENSIONS DYNA... par bjdc
CALCUL DE LA VALEUR MAXIMALE D'UN TABLEAU par Metrox

Commentaires et avis

Commentaire de coucou747 le 03/02/2009 12:29:29

#  for (int j = i; j <= n; j += i) {
# if (j % i == 0) {
# tab[j] = false;
# }
# }

comment ta condition pourrait-etre fausse ?

Commentaire de Virtuoooose le 03/02/2009 12:40:47

Exact, merci de faire remarquer cette erreur. Dans ce cas ci, la condition n'est plus utile.
Je modifie la source.

Commentaire de petifa le 04/02/2009 10:19:17

slt
hormis 2, les nombres paires ne sont jamais premier...
ce code peut donc être optimisé
Sinon si je ne me trompe pas 0 n'est pas un nombre premier ..

Commentaire de Virtuoooose le 04/02/2009 18:21:20

Normalement c'est corrigé :)

Commentaire de petifa le 04/02/2009 20:44:17

#  for (int i = 3; i <= n; i += 2) {
# // on utilise des pas de 2, car tout les nombres pairs ne sont pas premiers car 2 est premier.

Ce que tu fais est juste mais le cas des 2 n'est pas géré.
tab[4] = tab[6] = ... = true or ca devrait être false
donc ajoute juste après l'initialisation du tableau
#  for (int i = 4; i <= n; i += 2) {
# tab[i] = false;
# }

Commentaire de Virtuoooose le 04/02/2009 20:53:58

lol , est-ce bon cette fois ? merci en tout cas de ton aide petifa

Commentaire de petifa le 05/02/2009 11:11:50

non c'est toujours pas bon
#  if (i % 2 == 0) {
# tab[i] = false;
et si i = 2 => tab[2] = false
or ca devrait être vrai

Commentaire de Virtuoooose le 05/02/2009 14:08:56

Bon la c'est bon (enfin) , c'est juste que je voulais éviter deux faire 2 boucles for d'affilés pour l'initialisation du tableau mais c'est vrai qu'on peux pas trop faire autrement.

Commentaire de petifa le 05/02/2009 14:18:57

certes mais bon au moins en faisant i+=2 tu accélère le processus
le résultat m'a l'air juste :p

Commentaire de Virtuoooose le 05/02/2009 14:20:00

Merci de ton aide :)

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

probleme tableau 3 dimensions [ par lebobby ] j'ai un pb avec un tableau a 3 dimension car la troisieme est variable selon l'indice des 2 premiers.je m'explique plus clairement :String messages_CM Dessiner un tableau [ par Talboum ] Comment dessiner un tableau de string ?Par exemple, j'ai un tableau avec 3 elements (un, deux, trois) et je veux que mon applet affiche :_____________ tableau 3D [ par gloom ] salut bah voil g un probléme avec les tableaux 3 dimesnion ,comment peut on déclarer un tableau 3D sinon comment lui affecter un trcu un typre premet Tableau [ par salim01 ] quand je crée l'Objet Tableauje déclare ces variablesje crée le constructeur et la méthode et j'ai un messagecannot resolve symbol : TableauToujours q probleme de communication de dataInputStream et dataOutputStream [ par marsrepart ] j'ai un souci lorsque je fais communiquer 2 fluxje cree un tableau de bytes, dedans j'y mets à la suite : ** une string que je convertis en bytes pa passage de tableau en client/serveur [ par titou445 ] bonjour,je souhaiterais avoir des infos concernants l'envoie d'un tableau d'entier d'un client à un serveur.Quel est la commande à employer pour envoy Ajout d'element dans une JList [ par jonathan100 ] Bonjour, Voici un peu de code: String[] tableau_tampon = {"coucou"};JList ma_liste = new JList(tableau_tampon);Ce code va initialiser ma liste. Or lor fichier DXF OU DWG [ par papis ] papisBonjour, je fais un programme dont je dois générer un fichier DXF ou DWG. dans mon application j'ai une partie graphique de dessin avec les modes étirer image avec css [ par eax ] bonsoir,je souhaite mettre une image en fond dans un tableau (dans la balise TD). je souhaiterai que cette image soit étirée, qu'elle prenne toute la Comment faire un tableau de String [ par pellic ] Je Voudrai bien afficher le resulatat d'une selection dans une base de données, et afficher le resultat dans un JTextArea mais j'ai besoin d'un tablea


Nos sponsors


Sondage...

CalendriCode

Février 2010
LMMJVSD
1234567
891011121314
15161718192021
22232425262728

Consulter la suite du CalendriCode

 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,983 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales