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

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 3 févr. 2009 à 12:29
cs_Julien39 Messages postés 6414 Date d'inscription mardi 8 mars 2005 Statut Modérateur Dernière intervention 29 juillet 2020 - 13 févr. 2010 à 08:14

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/49158-nombres-premiers-par-le-crible-d-eratosthene-version-optimisee

cs_Julien39 Messages postés 6414 Date d'inscription mardi 8 mars 2005 Statut Modérateur Dernière intervention 29 juillet 2020 371
13 févr. 2010 à 08:14

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

cs_Julien39 Messages postés 6414 Date d'inscription mardi 8 mars 2005 Statut Modérateur Dernière intervention 29 juillet 2020 371
13 févr. 2010 à 08:13

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 !

Virtuoooose Messages postés 9 Date d'inscription mardi 27 mai 2003 Statut Membre Dernière intervention 8 février 2009
5 févr. 2009 à 14:20

Merci de ton aide :)

cs_petifa Messages postés 215 Date d'inscription dimanche 20 février 2005 Statut Membre Dernière intervention 10 mars 2014
5 févr. 2009 à 14:18

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

Virtuoooose Messages postés 9 Date d'inscription mardi 27 mai 2003 Statut Membre Dernière intervention 8 février 2009
5 févr. 2009 à 14:08

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.

cs_petifa Messages postés 215 Date d'inscription dimanche 20 février 2005 Statut Membre Dernière intervention 10 mars 2014
5 févr. 2009 à 11:11

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

Virtuoooose Messages postés 9 Date d'inscription mardi 27 mai 2003 Statut Membre Dernière intervention 8 février 2009
4 févr. 2009 à 20:53

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

cs_petifa Messages postés 215 Date d'inscription dimanche 20 février 2005 Statut Membre Dernière intervention 10 mars 2014
4 févr. 2009 à 20:44

# 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;
# }

Virtuoooose Messages postés 9 Date d'inscription mardi 27 mai 2003 Statut Membre Dernière intervention 8 février 2009
4 févr. 2009 à 18:21

Normalement c'est corrigé :)

cs_petifa Messages postés 215 Date d'inscription dimanche 20 février 2005 Statut Membre Dernière intervention 10 mars 2014
4 févr. 2009 à 10:19

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

Virtuoooose Messages postés 9 Date d'inscription mardi 27 mai 2003 Statut Membre Dernière intervention 8 février 2009
3 févr. 2009 à 12:40

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

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
3 févr. 2009 à 12:29

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

comment ta condition pourrait-etre fausse ?

Discussions similaires

Nombre de semaines dans l'année

Calcul du n-ième nombre premier

affecter la date du jour à une variable

poster une variable php dans un href

Choisir une date

Votre réponse

Discussions similaires