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"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
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

.1280130ldTy1,48*A]ké/weibmc:_35qaPr 7F=9o[f.;tRg26sSh)(punv050d0r0O0B0s0c0T0E0v0c0B0T0T0H010O0s0Y010406050T0Z0u0u0B0D0f040U0J0c0Z0_0J0!0E020B0u0Y0N0E0P0r130D0A0Z0r0T050p101214160~0Y04051B1u1E0p1B0~0d0s0#0.0:0=0@0V0s0Q0V0c1S0V0O0|050)0t0c0r1N0;0?011R1T1V1T0O1#1%1Z0O0D1C0O0V0.190T0Y0B0!0@0R011)1P010L0+0r0!1h0r1Z1 21261+291%2c0u2e040a0E0C0D0J0Y0J0T0s1c1e0%1}0D0D0r0v2z1u2g0!1C0p1{2L1^1`1_1!0d2i0@1V0!2b2w1Z1K1M0/1*2V0s2X0!0J2#1Z0Y2E1C2J2L2?0 201e2%272,0D130c0|0E0g2I2`0}2_2h2|1+2~30320R3521372J2U013c0B31040E0y3g2K0~3j3a0@3m3o0E0i3s3i2`3k3y320z3C3u3E3w3l0J2 3n320S3J382{1O3b3O3d3p0F3T3v3W3x3Y3Q3p0j3$3L3(3N3P3z0I3.393:3G040g0b3^3V2(3;3Z0g341v363K3_413{0g3f463h48402}3*3o0g3r4e3t3U3F4j0|0g3B4n2L2:0r2L2#2O0d1`2T3M0v2-2o0$1L1C4x2=363C054G0%4N49270n0|0%0L3C0E4p3M0!0L0|0v0D0s1$0r4P3%410{040X4:3/4a0|0!4_4U1+4?0W0w3 3k0q320E584~4h1+0T0d0|021q0J0O0N5g0Z5i5k5h5j543M5d57581m0!0#0J0s1(0Z1e1=0r0B0Z1}0!0O2b210O0E0O0J0Z0-1%0-2,0u0t2E0-4x0u5A0D5Z1a5Z0(2y1t4v4g3k5t3p580E1q1(4}5.4$3:5;5?1f5p5o5m5j5l5n3J5 5|4{045!5$5-2?4#4;270J0|0H4!69274?0K0m675?6n3b0|1#6m6h1+6j046l4v6g4`6o0|0K5a3k0n0v0|0e0D1r6K3M4?6r6E6u0@6B0k6y6G6v045`2?06686z3x6w0B0t6S3:6p6=415#0|3~4v6X016U0h6#4 6.046x6}6-6 6I6^276`3|7b500|6V6f6~6B6D7j786M0|0G3n0T4/776$0@4?716W7o6N047r0,7u6*6,7w014W040L3O725b740s7P3k0J56042*7T4%0t0|0D210Q7G4O784?4^7v73017d4d2^7,0|7z7n7J0!4|7f7x0|526s5 597o0|0s4Z7A7|6/6;7/7Q79046J8e3F877 8g7i366F7:7l7m8p6~7p046P6R8j6T0|535.848F8q8f7}6b2E5#0r5%8m6B0M8m8J0B0Y0Y2b0d8m7-8S8l8A6?81838G857J7L7N0D7Z3`0|0u0Z0c0_0Y1%8;417V876)8u780!7#047%0!7)8Z0|7.7@7J7=8}6i0|6!8a7:8J7S8%4=7_9g6%913h6~7y9r7R9a04828E8+8G6~8J769d7:6@9o2}8?8^8`8|9L7g048o3h8H7U6k9x7K7C7E7t8*8v7$0(0Z0D9t2K9W4%0|6c8N6e471u4R4y1F2;1u4A1u0O4Ca12R2M6:1%4z4K1A4T8f8L0x0L0B0n0r0x0V0y0|1m1o5^0-8D2^1H371B0l0E0:0E8{0B0v1(2Baz1/2X330R0E2,5R0E5G4,1d5Z5H0o4+0s2E0E8D1I1D1C9{7M3O0E8@8_0`1%0E2*0E0K0n0k0s0E8/0E0na/1e977)0X0R0haL0Wa/0La{a@028_0N0!0m8Da%1F370p0%0)0+0T04.