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

.128013kg[: r;)SĂ©/q(.loF4y,6b=ac15ud3t28_Pw7evp-fh0*T9mnRA]is050D0M0F0y0#0p0$0f0z0p0y0$0$0x010F0#0O010406050$0C0W0W0y0g0t040j0q0p0C0`0q0X0f020y0W0O0h0f0Y0M140g0m0C0M0$050l111315170 0O04051C1v1F0l1C0 0D0#0N0/0;0?0^0;0X0c0C0y0c0M0P0O0t0F0R1e0f0R0#0c0R0p1+0R0F0}050*0w0p0M1O0=0@011*1,1.1,0F1@1_1=0F0g1D1$0/1a0$0O0y0X0^0G011{1Q010Q0,0M0X1i0M1=2d2f2k1}2n1_2q0W2s040a0f0J0g0q0O0q0$0#1d1f0(2b0g0g0M0z2N1v2u0X1D0l1$2Z2729281?0D2w1R0#0X2p2K1=1L1N0:1|2-2/0X0q2?1=0O2S1D2X2Z33102e1f2^2l2|0g140p1=0y1)2S0Q0^030I0I0z2}0M1.2{0q0P0S0P0A0}0f0A1v0y34370~362v391}3b3d3f3h0M3j013l3n3p3r2:3u0P2i040f0G3B3D2f3F2X2,013K0y3e1D3g0R3i3k3m3o0(3U2|3W0E3y0E3$2W3E0 3*3I0^3-3/053;3?3Q3^3T2.3V3v0s3y0s411w433G381P3J0q3c3.3M3=3O3@3S3`4g3|3v0B3y0B4m3344373+484w4c3R3_3q4C3t3v0v3y0v4I4o454r474t3L3:3N3P4Q4f3s3W0L3y0L4Z3(4K3H4$3,4(4v4*4x4,4e4B4/3v0H3y0H4@2Y4_4q2_4|4u494b4y4d4A4S540P0V3y0V593)4L465e4)4a4+4z4R3{4U3w0S0}0A0S5r5b4M4}5g5y5j5A4T3W0A3x045S5I4p5K5f4O5i4-534h3w3Y0A3#0l3C424^5X5u4N4 4P525l5(0A3~5U405-3%5a5;4{5?5x505z4.5{4j5U4l605/2Y1G311v2?2$0D292+5u4R2=1M1D300M323E6f1D4R6w2v0#0D0^3m2X5R3M6D6F5k5B6I0f2A0M6L5P5m5T414#5d0b0}0(0Q6y0f635d0X0Q0}0z0g0#1^0M6y6)2l0|040n6?6X3a0}0X6|5t4{6_0i0e6y0 4n3(5X6K016G373W3Y5x7c5_6N3v2i6P2r6S694D3X1=6e6}1}0K3y0f7A714`5d0$0D0}021r0q0F0h7I0C7K7M7J7L777C1f7j0I6H3v5}7i6E7d6M5Q7Z2j6Q7q5%7s7!7v727E7G3Z7A1m2p0N0q0#1`0C1f240M0y0C2b0X0F2p2f0F0f0F0q0C0.1_0.2|0W0w2S0.6u0W7~0g8n1b8n0)2M1u79628y6B7V7$7e2f3W6b7#7-5`7s4j7o2B8J7l0P8H7;7D2l7F7z7A1r1`708A78353*7W7Y0P4F4*7W6T5(4F8N6R7%8:7s8-6W7=8V7@7_1g7R7Q7O7L7N7P7T8A7b8D7X7f4V6J9b8_5C4W8?8P7)0P4W2Z3C906@3J0}8o8q8x336(7w0^0q0}0x6%9s0^6_0d0!988(4L8*9d0P4;8.9g7r5C4;9k8^9U4:7u9q7_9G3,0}1@9F9A019C049E8A9z8}1}9I7U3+0b0z0}0U0g1s9`5u6_9K9=9(9/0T9,9@476 9L6x8)9b8+569S9l5m569X7k9maj3$9r9-0X9*0y0wa2730}0daz5d8p0}5H999-a40uaa8U9t049+aIab019_aRaN0^aF5UaD6^0}a59ya79DaM5c2l9|0}0r3.0$6=aVa,9^0}aLa69-a.04a:0-a?4J9`9O8F3v5oak9Y7.5C5oao7(5mb8as9%a}0}0Q4ta+4M0}0#bo5u0q7y042.bs640w0}0g2f1Xa!a_6`bFaX0#0}5,9MaWaTa`by6*ada@3+74768$b4ah9P5G9fal5{5Ebe9h5R5E9p7^907Bbkbw6$a|aSavaPaxbIbP04aCbU5=bqb~a4bR2l9/0x9;a(a}9}049 a1c2aA04bXb3bUb50X5R6V3g8/9Z3v5S7+7pba8K5Ccwb/b;cE9?bOb{9v0M8rb~9/0ob~b{0y0O0O2p0Dc50}6{cibSbwcW040iae7aag6L8+5+b%cz8Qc.b+cu5)9#b:cFb=aS6Z04bm0gc7aO0W0C0p0`0O1_d29Bbvbxb_cHbA04bC1Tb2afaS6_cYbNa^bJbLda9.0}a9dedq9)c#cZa#04a{ccb`bTdpbVbQdxbpdAdIa30}75c)6gc+7%c-7!cs9Tbb5R3~c?d!cv7:9$c{cE9(b{aQdOcjc1d;c!d4d60{d9dBbGa%3EcGdyc9dta~b0a=dS8B0fco5R8HdYb(7s0A8M7,c:9mehc_atc}bB0)0C0g8#dFcH9u2S8pcK9x4o990l6A6h6v6j6s1v0F6meK2)2!ax1_2Z6k1Be95uey0I0Q0y0b0M0I0R5}1n1p8Z0.cl6x1I3F1C0Z0f0;0fd80y0z1`2Pe^212/3z0G6P8e0.846/1e8n850k6.0#2S0fbX1J1E6z3pc 4t0fd_d71_ea1f0d0b0T0#0fd00f0bfs0fdi1X0n0G0u6P0iea0QfAfw02d60h0X0!bXeFe:780(0*0,0$04.