Nombres premiers: crible d'Eratosthène
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
5 sept. 2013 à 20:05
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 21 sept. 2013 à 16:57
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 21 sept. 2013 à 16:57
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/100096-nombres-premiers-crible-d-eratosthene
https://codes-sources.commentcamarche.net/source/100096-nombres-premiers-crible-d-eratosthene
21 sept. 2013 à 16:57
On aurait donc pour chaque char un groupe de 8 bits que l'on associerait à 8 booléens.
Exemple :
char* reserve(int n) { return malloc(n/8+1); } void set(char* tab, int i, int b) { if (b) tab[i/8] |= (1 << i%8); else tab[i/8] &= ~(1 << i%8); } int get(char* tab, int i) { return (tab[i/8] >> (i%8))%2 != 0; }On adapte alors facilement le programme avec ces nouvelles fonctions, et on optimise ainsi la consommation mémoire :
char* sieve3(int m) { int i,j,p,pp, h=(m-1)/2; char* sv = reserve(h); for (i=0; i<h; i++) set(sv,i,1); for (i=0, p=3, pp=9; pp<=m; i++, p+=2, pp = p*p) if (get(sv,i)) for (j=(pp-3)/2; j<h; j+=p) set(sv,j,0); return sv; }Cependant, comme on rajoute des opérations, on diminue aussi la rapidité du programme. On ne peut pas tout avoir...
21 sept. 2013 à 09:49
Merci pour votre commentaire: la traduction que vous proposez est très bien faite.
Vous m'avez encouragé de me "remettre" à C et de présenter prochainement une "optimisation" basée sur votre fonction.
De plus, comme je soupçonne que Javascript utilise 64 bits par booléen, je vais essayer d'ajouter ici un "Sieve4.js" où sv est basé sur un string.
5 sept. 2013 à 23:55
Par contre (et sans surprise), c'est bien plus rapide en C qu'en JavaScript, même s'il faudrait faire des tests comparables, notamment sur la même machine.
max = 100000000
temps = 461 ms (moyenne de 100 exécutions)
5 sept. 2013 à 20:05
En C :
#include "stdlib.h" char* sieve3(int m) { int i,j,p,pp, h=(m-1)/2; char* sv = malloc(sizeof(char)*h); for (i=0; i<h; i++) sv[i] = 1; for (i=0, p=3, pp=9; pp<=m; i++, p+=2, pp = p*p) if (sv[i]) for (j=(pp-3)/2; j<h; j+=p) sv[j] = 0; return sv; }Remarque 1 : je propose une légère optimisation, en remplaçant pp=p*p par pp+=(p-1)<<2, mais je ne suis pas certain que cela améliore vraiment le calcul...
Remarque 2 : vu que le type booléen n'existe pas en C, j'ai mis des char, du coup la mémoire sera en char[Max/2], mais de toute façon je ne sais pas comment est gérée la mémoire en JavaScript mais un booléen prend surement aussi un octet en mémoire comme le char du C.
Voici un main de test :
#include "stdio.h" int main() { int i,m; char* sv; printf("m="); scanf("%d",&m); sv = sieve3(m); for (i=0; i<(m-1)/2; i++) printf("%d : %sn", 3+2*i, sv[i] ? "premier" : "pas premier"); return 0; }