Crible d'Eratosthène

Un nombre premier est un nombre entier naturel qui admet exactement deux diviseurs distincts entiers et positifs : 1 et lui-mĂŞme.

Le crible d’Ératosthène permet de déterminer les nombres premiers plus petit qu’un certain nombre n fixé.

On considère pour cela un tableau tab de nbooléens, initialement tous égaux à True, sauf tab[0] et tab[1] qui valent False, 0 et 1 n’étant pas des nombres premiers.

On parcourt alors ce tableau de gauche Ă  droite.

Pour chaque indice i :

  • si tab[i] vaut True : le nombre i est premier et on donne la valeur False Ă  toutes les cases du tableau dont l’indice est un multiple de i, Ă  partir de 2*i (c’est-Ă -dire 2*i, 3*i ...).

  • si tab[i] vaut False : le nombre i n’est pas premier et on n’effectue aucun changement sur le tableau.

On dispose de la fonction crible, incomplète et donnée ci-dessous, prenant en paramètre un entier n strictement positif et renvoyant un tableau contenant tous les nombres premiers plus petits que n.

Sieve of Eratosthenes animation.gif
By CC BY-SA 3.0, Link

Auteur SKopp sur Wikipedia allemand

Compléter la fonction crible

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013f06S:d=F4yr./oTpg2mcb1w9R37ve[ l*8,+P5)ti]kn;ua(_shq050g0D0O0V0P0G0Y0F0u0G0V0Y0Y0h010O0P0q010406050Y0U0t0t0V0l0k040e0o0G0U0^0o0S0F020V0t0q0T0F0z0D120l0!0U0D0Y050n0 1113150}0q04051A1t1D0n1A0}0g0P0C0-0/0;0?0Z0P0r0Z0G1R0Z0O0{050(0v0G0D1M0:0=011Q1S1U1S0O1!1$1Y0O0l1B0O0Z0-180Y0q0V0S0?0s011(1O010b0*0D0S1g0D1Y1~20251*281$2b0t2d040a0F0L0l0o0q0o0Y0P1b1d0$1|0l0l0D0u2y1t2f0S1B0n1`2K1@1_1^1Z0g2h0?1U0S2a2v1Y1J1L0.1)2U0P2W0S0o2!1Y0q2D1B2I2K2=0~1 1d2$262+0l120G0{0F0w2H2_0|2^2g2{1*2}2 310s3420362I2T013b0V30040F0A3f2J0}3i390?3l3n0F0j3r3h2_3j3x310M3B3t3D3v3k0o2~3m310d3I372`1N3a3N3c3o0B3S3u3V3w3X3P3o0I3#3K3%3M3O3y0y3-383/3F040w0c3@3U2%3:3Y0w331u353J3^403`0w3e453g473 2|3)3n0w3q4d3s3T3E4i0{0w3A4m2K2/0D2K2!2N0g1_2S3L0u2,2n0#1K1B4w2;353B054F0$4M48260R0{0$0b4O3$400x314Z3.490b0{0u0l0P1#0D4(4T1*0`040W4=4g3a0{0S4{3j4^0N0f3~3j4$3o0F59503L0Y0g0{021p0o0O0T5g0U5i5k5h5j1l0S0C0o0P1%0U1d1;0D0V0U1|0S0O2a200O0F0O0o0U0,1$0,2+0t0v2D0,4w0t5v0l1s4u4f3j5d31590F0q195U0%2x0,1p1%0S0m5l5n5^5j5`0T3I5)0F4o3L0S0{5V5X5Z2=604!260o0{0h3B694)264^0E0Q5~5)613_0{1!6f6o406c046e4u6g4?0?6j5b3/0R0u0{0p0l1q6D404^6l6y6t6b0{0H6s6a4}044 5!5 6Q6W6r4u6#6B0{0E6L265W0{3}6(6V6*040Q0J6U6h6$0V0v6-4@6+700?6/3{73016N6{6A016v6x686)016F0{0i3m0Y4;6=6|6@6`6P6?7h6G047k0+7n2=066!7t4V040b3N7a4|3w0{0P7I3j0o572)7N620v0{0l200r7z4N7t4^4`7o7b636X7752546Z5 6n7D7L4Y7s7p3k6q6~7,727(7J7`047M7 510{0Q7.7A7:8a6z807*650D5Y776v0m777*0V0q0q2a0g7}4_8l7L8s0N6m8b7;7_7*0t0U0G0^5+7Z3g8c7O6d7S3/754c2@7t6v6T84628v6y7B8z8A7b7E0x1Q1$8N490{8D8F0_8*7^7b6v028F5}8=8d4~8s88468!8b7g7*6%8R7_6C8V6p048.8G8;967b798{8L6w8+4U7v7x7m6f8Z917C8B8-8E9d8I2J8K3L7d9l6W9c8:9y3o7g6v0K9D7K829q9t8$7V0%0U0l6Y7f7t8e2D5W8g67461t4Q4x1E2:1t4z1t0O4B9:2Q2L6~1$4y4J1z4S809!0X0b0V0R0D0X0Z0A0{1l1n5;0,8 3g1E361A0L0:0F2A9!135;ag0}0n0$0(0*0Y04.