begin process at 2012 02 15 11:00:18
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
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 :
3 / 10 - par 1 personne
3,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
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 :6 921
Auteur : Virtuoooose

Ecrire un message privé
Commentaire sur cette source (12)
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

IMPLÉMENTATION DE L'ENSEMBLE C AVEC JAVA par Scupper
CALCUL D'EXPONENTIEL ( PRÉCISION MODIFIABLE) par Scupper
Source avec Zip TRANSFORMATION D'UNE EXPRESSION ARITHMETIQUE (INFIXÉ) EN POS... par billatosco
PROBLÈME DES N-REINES par jojolemariole
Source avec Zip ARRAYMATRIX -MATRICE MULTIDIMENSIONELLE ET GÉNÉRIQUE- , IMP... par labandus
Toutes les sources de la catégorie Maths et Algorithmes

 Sources en rapport avec celle ci

CALCULER LA FACTORIELLE JUSQU'À 5409! AVEC JSP ET L'AFFICHER... par Scupper
TEST DE PRIMALITÉ OPTIMISÉ par Julien39
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

Commentaires et avis

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

#  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 :)

Commentaire de Julien39 le 13/02/2010 08:13:00 administrateur CS 3/10

De toutes petites améliorations te permetraient d'accélérer considérablement le programme, tu n'est pas obligé de tester les nombres jusqu'ç n, tu peux t'arreter à racine de n, si un nombre n'est pas premier, il adment un diviseur plus petit que ca racine.

Ensuite, tu pourrais stocker les nombres premiers que tu as trouvé dans une liste et ne tester la division que pour ces nombres là, au lieu de retirer les multiples de deux, tu retire tout les nombres composés.

Ce n'est qu'un début mais avec ta méthode pour savoir si 101 est premier, tu vas effectuer 50 calculs, en ajoutant les améliorations que je te propose, tu ne feras que 4 calculs, tu vas apeu pres diviser le temps d'éxécution par 10 !

Commentaire de Julien39 le 13/02/2010 08:14:11 administrateur CS

Et ausi, c'est une drôle d'idée de stocker les boolées dans un tableau, ca t'oblige a reparcourir ton tableau à la fin ...

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

Comparez les prix


Archos Tablette PC ARNOVA ARNOVA 10 4GB
Entre 200€ et 210€

Visiter le guide achat

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

Photothèque

Photo Green Energy Solutions With Light Bulb Morphed Into LandscapePhoto Beautiful woman in a bikini meditating on the beach
Photo Beautiful El Capitan Yosemite National Park 

Visiter la photothèque
 
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,671 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)