Discussion:Crible d'Ératosthène

Bonjour,

La table a été construite avec un programme en perl dont voici le source : Pour l'utiliser taper en ligne de commande :

perl crible.pl > prem.html

et éditer le fichier obtenu pour supprimer le </tr> du début.

Ce n'est pas la perfection.

COLETTE 21:20 mar 29, 2003 (CET)

#!/usr/bin/perl

$N=500;

for ($i=0; $i<$N; $i++) {
    $a[$i]=1;
    $c[$i]=0;
}

$a[0]=0;
$a[1]=0;
$i=2;
$k=0;
while ($i<=$N)  {
    $paspremier=1;
    while ($paspremier && ($i<=$N)) {
	$paspremier=($a[$i]==0);
	$i++;
    }
    $i--;
    $k++;
    $c[$i]=$k;
    $j=2;
    while ($j*$i<=$N) {
	if ($a[$i*$j]==1)
	{
	    $c[$i*$j]=$k;
	}
	$a[$i*$j]=0;
	$j++;
    }
    $i++;
}

@cou=("yellow", "\"#0000ff\"", "\"#ff0000\"", "\"#deff7d\"", "\"#de7fff\"", "\"#1571ff\"", "\"#15ff8c\"", "\"#92ba8c\"", "\"#92008c\"", "\"#b04f6f\"", "\"#b04fe6\"", "\"#b0ffe6\"", "\"#1f99d5\"", "\"#ad26d5\"", "\"#deabd5\"", "\"#1fffff\"", "\"#ffff23\"", "\"#ffe09d\"", "\"#f9cdff\"", "\"#f9cd15\"", "\"#5affbc\"",
"\"#7f7fe2\"", "\"#51964f\"", "\"#ff9782\"", "\"#0077c0\"", "\"#00cbcb\"", "\"#8c38cb\"", "\"#d5aecb\"", "\"#d5ae4f\"", "\"#00d9ff\"", "\"#a59758\"",  "\"#ffc6c7\"", "\"#ffc0c0\"",
"yellow", "\"#0000ff\"", "\"#ff0000\"", "\"#deff7d\"", "\"#de7fff\"", "\"#1571ff\"", "\"#15ff8c\"", "\"#92ba8c\"", "\"#92008c\"", "\"#b04f6f\"", "\"#b04fe6\"", "\"#b0ffe6\"", "\"#1f99d5\"", "\"#ad26d5\"", "\"#deabd5\"", "\"#1fffff\"", "\"#ffff23\"", "\"#ffe09d\"", "\"#f9cdff\"", "\"#f9cd15\"", "\"#5affbc\"",
"\"#7f7fe2\"", "\"#51964f\"", "\"#ff9782\"", "\"#0077c0\"", "\"#00cbcb\"", "\"#8c38cb\"", "\"#d5aecb\"", "\"#d5ae4f\"", "\"#00d9ff\"", "\"#a59758\"",  "\"#ffc6c7\"", "\"#ffc0c0\"",
"yellow", "\"#0000ff\"", "\"#ff0000\"", "\"#deff7d\"", "\"#de7fff\"", "\"#1571ff\"", "\"#15ff8c\"", "\"#92ba8c\"", "\"#92008c\"", "\"#b04f6f\"", "\"#b04fe6\"", "\"#b0ffe6\"", "\"#1f99d5\"", "\"#ad26d5\"", "\"#deabd5\"", "\"#1fffff\"", "\"#ffff23\"", "\"#ffe09d\"", "\"#f9cdff\"", "\"#f9cd15\"", "\"#5affbc\"",
"\"#7f7fe2\"", "\"#51964f\"", "\"#ff9782\"", "\"#0077c0\"", "\"#00cbcb\"", "\"#8c38cb\"", "\"#d5aecb\"", "\"#d5ae4f\"", "\"#00d9ff\"", "\"#a59758\"",  "\"#ffc6c7\"", "\"#ffc0c0\"",
"yellow", "\"#0000ff\"", "\"#ff0000\"", "\"#deff7d\"", "\"#de7fff\"", "\"#1571ff\"", "\"#15ff8c\"", "\"#92ba8c\"", "\"#92008c\"", "\"#b04f6f\"", "\"#b04fe6\"", "\"#b0ffe6\"", "\"#1f99d5\"", "\"#ad26d5\"", "\"#deabd5\"", "\"#1fffff\"", "\"#ffff23\"", "\"#ffe09d\"", "\"#f9cdff\"", "\"#f9cd15\"", "\"#5affbc\"",
"\"#7f7fe2\"", "\"#51964f\"", "\"#ff9782\"", "\"#0077c0\"", "\"#00cbcb\"", "\"#8c38cb\"", "\"#d5aecb\"", "\"#d5ae4f\"", "\"#00d9ff\"", "\"#a59758\"",  "\"#ffc6c7\"", "\"#ffc0c0\"",
"yellow", "\"#0000ff\"", "\"#ff0000\"", "\"#deff7d\"", "\"#de7fff\"", "\"#1571ff\"", "\"#15ff8c\"", "\"#92ba8c\"", "\"#92008c\"", "\"#b04f6f\"", "\"#b04fe6\"", "\"#b0ffe6\"", "\"#1f99d5\"", "\"#ad26d5\"", "\"#deabd5\"", "\"#1fffff\"", "\"#ffff23\"", "\"#ffe09d\"", "\"#f9cdff\"", "\"#f9cd15\"", "\"#5affbc\"",
"\"#7f7fe2\"", "\"#51964f\"", "\"#ff9782\"", "\"#0077c0\"", "\"#00cbcb\"", "\"#8c38cb\"", "\"#d5aecb\"", "\"#d5ae4f\"", "\"#00d9ff\"", "\"#a59758\"",  "\"#ffc6c7\"", "\"#ffc0c0\"");

print "<table border=\"1\" cellspacing=\"0\" cellpadding=\"2\">";

$j=0;
for ($i=0; $i<$N; $i++) {
    if ($i % 20==0) {
	$b[$j++]="</tr>\n";
	$b[$j++]="<tr>";
    }
    if ($a[$i]!=0) {
	$b[$j++]="<td bgcolor=$cou[$c[$i]]>";
	$b[$j++]=$i;
	$b[$j++]="</td>";
    }
    else {
	$b[$j++]="<td><font color=$cou[$c[$i]]><strike>";
	$b[$j++]=$i;
	$b[$j++]="</strike></font></td>";
    }
}



print "@b";

print "</table>";

Deux versions C

Pourquoi garder la première des 2 versions vu qu'elle est nettement moins efficace ?

Je propose de supprimer simplement la première.

Zenon

ajout d'un code bash

j'ajoute le code suivant :

#!/usr/bin/bash
#
# crible d Eratosthene

erat()
if (($1**2 > ${!#})); then echo $@;
else
    a=$1; b="";
    while shift; (($#));
    do (($1%$a)) && b+=" "$1;
    done;
    echo $a $(erat $b);
fi

erat {2..100}

bash a le mérite d'être un langage largement répandu (du moins sur les machines linux).

multi-plateformes ???

--Lf69100 (discuter) 30 août 2015 à 20:08 (CEST)

partie algorithme trop longue...

amha il faudrait faire plus simple en enlevant le détail par étapes.

Algo bash tout aprticuliérement incomprehensible

Il faudrait plutot mettre du pseudo code tellement l'ago en bash est horrible à comprendre.

un pseudo code serait bienvenu en complément, mais l'algo bash présente l'avantage d'être un code concis, fonctionnant réellement, et qui plus est dans un langage très répandu (toutes les distributions linux le proposent par défaut).

J'ajoute tout de même des commentaires dans le code.

--Grondilu (d) 20 février 2010 à 20:00 (CET)

Le retour du beotien

Ma question est simple et s'adresse aux matheux: quel est le principe mathématique de crible; L'article explique parfaitement son fonctionnement Mais la différence avec un autre crible c'est quand on replace d'ensemble de depart ou quand on change la methode de calcul des nombres composés? L'artcle semble muet i/e supposons que j'écrive une autre méthode pour lister les nombres premiers: qu'est ce qui fera que cette méthode soit une version d'Eratosthène ou un crible différent?

Bonjour. Une addition récente à l'article explique mathématiquement (et non informatiquement) comment le crible fonctionne: il crée par itération une suite d'ensembles complémentaires dans N (D(k) et G(k)) qui se définissent comme suit: D(k)={ensemble des entiers divisibles par au moins un entier premier de rang inférieur ou égal à k} et G(k)={ensemble des entiers qui ne sont divisibles par aucun entier premier de rang inférieur ou égal à k}. Tous les D(k) et G(k) ont une densité, et la formule de calcul est indiquée dans le paragraphe concerné. J'espère que ceic apportera des éléments de réponse à votre question.--Olinone (discuter) 14 mars 2021 à 10:19 (CET)

---

Jérôme ----

D'accord, la page se précipite un peu vite dans les algorithmes, et rien ne date plus vite qu'un langage...

Pour rester simple, on pourrait rappeler :

• que la méthode initiale (définie vers l'an -200) fait que 2 élimine ses multiples, puis 3 les siens, 5 les siens etc, sans se soucier clairement de minimiser le travail, les nombres composés risquant d'être éliminés plusieurs fois, 30 étant éliminé au titre de 2, 3, 5; ou 30030, au titre de 2, 3, 5, 7, 11 et 13 ;
• pour une version plus rapide, on remarque que pour un nombre premier p, compte tenu de ce qui a déjà été éliminé au titre des nombres premiers inférieurs, il suffit de commencer l'élimination à p², et pour p>2, les multiples pairs ayant déjà été éliminés, de procéder de 2p en 2p ; pour 23, l'élimination commencera donc à 529, et se poursuivra de 46 en 46 (au lieu de commencer à 46 de 23 en 23); de plus, l'élimination peut s'arrêter dès que p² excède la borne qu'on s'est donné ;
• cette seconde version est en principe plus rapide ; mais cela dépendra du mode de stockage des nombres candidats, soit dans une table de taille fixe soit dans une liste plus courte à chaque étape.

--Lf69100 (discuter) 29 août 2015 à 16:10 (CEST)

Crible de Hoare

C'est le dual multi-tâches du crible d'Eratosthène. Je prend la liberté de l'insérer dans l'article. Il se programme aisément en CSP, occam, Ada... et peut être simulé à l'aide d'une liste dans les langages traditionnels.

Je laisse la communauté

• doter ce crible d'une illustration animée
• décider si ce crible mérite sa propre page, ce qui permettrait de le raccorder aussi à la tribu des méthodes generate and test.

Lf69100 (discuter) 10 septembre 2015 à 12:14 (CEST)

Pas d'animation en français ?

Sur Commons, il n'y en a pour l'instant qu'en polonais, en anglais, en allemand ou en italien. Anne, 7/7/2018

Crible euclidien

Le crible le plus rapide actuellement se base sur la multiplication des nombres premiers entre eux. Aucun multiple n'est éliminé, c'est le produit des NP (qui est très grand) qui est comparé aux n impairs successifs. Je peux fournir un texte descriptif de ce crible moyennant l'assurance qu'il sera publié dans une revue spécialisée. 86.223.96.220 (discuter) 1 décembre 2020 à 15:28 (CET) Ianop

--Olinone (discuter) 30 mars 2021 à 18:12 (CEST)

Probabilité et densité

Puisque le crible d’Ératosthène s’effectue sur une liste finie d’entiers, on peut très bien y parler de probabilité uniforme et pas de densité. Cette partie sur la probabilité ne parle pas vraiment du crible et ne l’utilise pas non plus. Elle est pour moi hors sujet. Ambigraphe, le 13 mars 2021 à 15:07 (CET)

Bonjour. Je suis un peu surpris des remarques d'Ambigraphe, et vais essayer d'y répondre. Il y a 2 remarques distinctes:

• la partie sur la "probabilité" ne parlerait pas vraiment du crible. Je pense qu'au contraire elle lui est intimement reliée...mais peut être n'ai-je pas été assez clair pour montrer ce lien. En fait la première partie de ce paragraphe montre comment fonctionne mathématiquement (et pas sous la forme d'un programme informatique) le crible, et quelles suites couplées d'ensembles (D(k), G(k)) sont créées par itération en l'utilisant. Puis s'intéresse aux densités/probabilités de ces suites d'ensembles. Je ne pense donc pas que ce passage soit hors sujet, mais propose d'en clarifier le texte le relier plus explicitement au crible.
• densité et probabilité: "puisque le crible le crible d’Ératosthène s’effectue sur une liste finie d’entiers" est une affirmation que je ne comprends pas, ou du moins qui ne s'applique pas aux ensembles D et G bâtis par le crible et examinés dans le paragraphe en cause. Au contraire chacun des ensembles apprtenant à l'une de ces deux suites est infini (par exemple: le nombre d'entiers pairs est infini, celui des nombres qui ne sont divisibles ni par 2 ni par 3 l'est également, etc...). Et c'est bien pour cela que les propriétés recherchées s'appliquent à des densités et non des probabilités. Je crois que la confusion vient du fait que la plupart des exemples d'utilisation du crible citées dans la littérature se limitent à la recherche d'entiers premiers inférieurs à une certaine valeur: les auteurs de ces exemples ne s'intéressent pas à ce qui se passe au-delà de l'horizon fini qu'ils ont pré défini. C'est au contraire très exactement ce que le paragraphe fait, et c'est une preuve supplémentaire, s'il en était besoin, qu'il est bien entièrement relié au crible et à ses propriétés.

J'espère que ces clarifications seront convaincantes.--Olinone (discuter) 14 mars 2021 à 10:10 (CET)/*

« la plupart des exemples d'utilisation du crible citées dans la littérature se limitent à la recherche d'entiers premiers inférieurs à une certaine valeur » : c’est bien pour cela que votre section n’a pas lieu d’être sur Wikipédia. Si aucune source ne présente ces ensembles D(k) et G(k), ils n’ont rien à faire ici. J’ai bien compris que vous êtes de bonne volonté et que vous ne cherchez qu’à ajouter du contenu mathématiquement correct, mais l’objet de Wikipédia se restreint au savoir déjà publié. Ambigraphe, le 14 mars 2021 à 13:38 (CET)

Merci Ambigraphe de votre prompte réponse. Je note que l'argument d'erreur de raisonnement mathématique a disparu. Reste celui de la référence à des travaux déjà publies. Je crois que lalectrue attentive de la référence que j'ai donnée est très exactmetn ce que vous cherchez. Vous trouverez en bas de la page 80 le texte suivant: "denote by A the set of all natural numbers that are not divisible by any of the ai's. Then the set has a density d(A)..." Ce qui est appelé A dans cette référence est très exactement ce que j'ai nommé G dans ma contribution! J'espère que ce point va enfin répondre à vos dernières remarques.--Olinone (discuter) 15 mars 2021 à 12:12 (CET)

Vous persistez à utiliser les termes de probabilité. En outre, la partie sur la densité aurait plus sa place sur l’article « Densité asymptotique » comme vous l’avait suggéré Anne Beauval. Ambi[[Discussion Probabilité et densité */ Suite à vos suggestions, je transfère la totalité du chapitre "densité" vers l'article "densité asymptotique".--Olinone (discuter) 30 mars 2021 à 18:12 (CEST)]], le 15 mars 2021 à 17:22 (CET)

Version récursive

Cette version n'est pas claire :

• elle prétend que son argument est un tableau, l'appel récursif ne précise pas comment est calculé le nouvel argument, qui est forcément un nouveau tableau, l'algo est incomplet
• pour que ça fonctionne le tableau argument doit toujours être ordonné, ça n'est pas précisé

Si l'idée est celle du crible d'Ératosthène, il y a quand même recalcul à chaque étape d'un nouveau tableau ; certes on peut oublier le premier une fois le second calculé. Mais on s'éloigne un peu de la simplicité d'origine. J'ai des doutes sur la pertinence de cette section. Proz (discuter) 25 septembre 2024 à 11:00 (CEST)

Idem. Cela semble trop compliqué. C'est Grondilu (d · c · b) qui semble à l'origine de ce pseudo-code, quel est son avis ? Jean-Christophe BENOIST (discuter) 25 septembre 2024 à 11:18 (CEST)

Je ne me souviens plus très bien du contexte dans lequel j'ai écrit ça. C'était probablement dans le même temps où j'avais posté un code similaire sur rosettacode. Ça peut être considéré comme un travail inédit donc je ne vois pas d'objection à sa suppression.--Grondilu (discuter) 25 septembre 2024 à 15:04 (CEST)

! Ok, merci de ta réponse, et merci à JCB d'avoir pensé à te contacter. Proz (discuter) 25 septembre 2024 à 16:01 (CEST)