Aller au contenu

Crible d'Ératosthène

Le cadre

⚠ Exercice d'optimisation

On suppose que vous avez déjà résolu la première version du Crible d'Ératosthène. On propose ici de montrer quelques petites améliorations. Un autre problème sera consacré pour d'autres améliorations importantes.

Objectif
Construire rapidement un tableau de primalité des entiers de \(0\) inclus à \(n\) inclus.
Méthode
On peut utiliser le crible d'Ératosthène. Vous avez déjà rencontré une première version qui ressemble à :
Code Python - version 1
🐍 Script Python
def ératosthène(n):
    crible = [True] * (n + 1)
    crible[0] = False  # 0 n'est pas premier
    if n > 0:
        crible[1] = False  # 1 n'est pas premier
    for p in range(2, n + 1):
        if crible[p]:
            # p est premier
            for kp in range(2*p, n + 1, p):
                # kp est un multiple de p, donc non premier
                crible[kp] = False
    return crible

On peut vérifier ceci avec le test ci-dessous

🐍 Console Python
>>> limite = 20
>>> primalite = eratosthene(limite)
>>> primalite_brute = [est_premier(i) for i in range(limite + 1)]
>>> primalite == primalite_brute
True
L'objectif de l'exercice est d'améliorer la fonction eratosthene en suivant les conseils suivants :

  1. Remplacer la ligne for p in range(2, n + 1): par une structure avec une boucle while.
  2. Remplacer la ligne for kp in range(2*p, n + 1, p): par for kp in range(p*p, n + 1, p):, en effet les multiples de \(2p\) inclus à \(p^2\) exclu ont déjà été cochés, on peut donc commencer à \(p^2\).
  3. En déduire que quand \(p×p > n\) il n'y plus de nouveaux multiples à cocher. Ils ont tous déjà été cochés. C'est une propriété mathématique : « Si un entier \(n\) est composé, alors il possède un diviseur premier inférieur ou égal à \(\sqrt{n}\) ». Modifier la boucle while en conséquence.
  4. Tester votre fonction eratosthene_V2 en la confrontant à eratosthene et à une méthode par force brute.

Génération des nombres premiers

Quand vous aurez terminé, vous pourrez tester une astuce avec Python pour générer la liste des nombres premiers à partir du tableau de booléens primalite.

Lire la documentation au sujet de itertools.compress

🐍 Console Python
>>> from itertools import compress
>>> limite = 20
>>> primalite = eratosthene(limite)
>>> list(compress(range(limite + 1), primalite))
[2, 3, 5, 7, 11, 13, 17 ,19]

Pour tester cela, construire une fonction telle que somme_premiers(n) renvoie la somme des nombres premiers jusqu'à \(n\).

Exemples
>>> somme_premiers(5)
10
>>> somme_premiers(20)
77
Remarque

Vous ajouterez tous les tests utiles aux différentes étapes.

###(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 : /
.9888.128013x/.Tr;nbOylaeê%u)*dV6çz3^m?(P+02è-@U],59fq!78 N_o=pcwgvF41kRIéhtsàSLC[jDi:E050u0o0;0n0}0m0=0V0#0m0n0=0=0Z010;0}0!010406050=0r0B0B0n0g0l040@0Y0m0r1g0Y0i0V020n0B0!0h0V0-0o1q0g0R0r0o0=050d1n1p1r1t1l0!04051Y1R1#0d1Y1l0u0}0(181a1c1e0:0}0%0:0m1?0:0;1j05130j0m0o1.1b1d011=1@1_1@0;1 211}0;0g1Z0;0:231:010Q150o0i1E0o01181w0=0!0n0i1e0H1}2w2y2k252n212q0B2s040b0V0E0g0Y0!0Y0=0}1z1B112u0g0g0o0#2W1R2D0i1Z0d2i2,2f2h2g1~0u2F1e1_0i2p2T1}1+1-19242_0}2{0i0Y2 1}0!2#1Z2*2,3d1m2x1B312l360g1q0m1j0V0+2)3h1k3g2E3j253l3n3p0H3s2y3u2*2^013z0n3o040V0z3D2+1l3G3x1e3J3L0V0*3P3F3h3H3V3p0O3Z3R3#3T3I0Y3m3K3p0w3*3v3i1/3y3/3A3M0T3@3S3`3U3|3;3M0U403,423.3:3W0P483w4a3%040+0G4f3_324b3}0+3r1S3t3+4g4o4i0+3C4t3E4v4n3k443L0+3O4B3Q3^3$4G1j0+3Y4K3!4w4F4c4P3)4S4D4N4W4j3?4Z4M3-4y3 4)414x4O4j474.494:4$0+4e4@4U3{4$0H4l4}4E4 3}0H4s3d4!4+4;0H4A594*4h5c4J5f4/4V564R5k4^5m450H4Y5p4~43504(5v545x564-5A4#564?5F5b504|5J5h4$0z525N4_3}0z584u5g5T450z5e5X5l555!5j5%5q5)3L0z5o5,5w4p5!5u5=5B5@5/5z5`5G5!5E5 5K5U5I635O5U5M675Z3L0*5R6b5r6d5W4C5Y6h1j0*5$6k5(5C450*5+6q5-6s6d5;6w5?4i0*5_6B5{6D5~6G606d626K646t666O686t6a6S6c1j0O6f6W6m040O6j4L6r5|6Y6p6*6x6,6%6v6/6C4;0O6A6@6H6_6F6|6L6Y6J706P3L0O6N746T766R796X6%6V7d6$0w6!7h5.1j0w6)4T6}4$0w6.2,3a0o2,2 2/0u2h2@3-0#372L101,1Z7w3c3t3Z057F117M5?0,1j110Q7O6+0$3p7Y6:0i0Q1j1P0;0X7w0B0}0o0g7$5?1i040D7?6H1j0i7{3H7^0s0~3*0V850V6l257U040}7X4S876+0i7}3Z8f6:0Y1j020m0;0h8j881e7/1j7u8t017^834Z868D8k7T1j2#0;0r0g7~8e8y0,0#1j0)3K0=0o84868O1j0Q3/8s8g7V8$8l7!8b8M3d8F6H0j8H2y0%8V4S8y7^7`8_6+8v048x6+7^0N8)6C8i8}6:818B598E8X6+0#0+1j033q1C8p1H2@8o8q0V8-4u9d858Y8b8d8.8y8h049s3E8/3H8m040q957|040u9K9G1j0Z0Z9O3-8 7k7S5{8A8W9u9e6:9g9i0V2@7+0V0r2X1,0}8U8K9*220i0N0V0n1y2#0V1N220+0V129r9!9#9F3-8a8I8K9D2+a84a8P8R8T8^9c9$8G04ab8L9Tag8Q040f0g1O3*065aag7V0o9y7N7Z7#986C7)047;0n0;2T2i2pakaF991j8|3f8%9C7 3-9aa69A1j0#0g0}20aS9E8y9H9S8N921j0`a!as1javaxaI9Y1j0Mar4o9H0tb32l8{a`4x979z6+9H0Fb7258 7p8`1j0sa%aYa*a,21bab8a^btbi0}1j9Wbl04b2a?8l9Qbh1eah048S16a.aeaf4o9(049j0G9r009,2x177.7:7=8Cam5{8a8cbH3Ibc3tbP2l9H020%8qb,9Vbw1e9Zb%9da(04bqa-b{8zbva 3Hbjc47^bDbdbF04a=cd7TatbL8U8jb:25bR9ja20ibW0=0;0VbYcw2#7/7;bo6:8a8!b$ch9L0!b,0Y8+34b,0i8;ao8?bN9X80aVc48 91aU0494bE96aZc%5{bfb_by4jcabm9b9t9u9wb+c*3$a)a+c3c7a#c6aX7%1jcJc 4acbc=4Ca7b(3Hcpcwa3cucy1Kb#a69#9wcFcO1j0,d5cH9GcMad3M9AcQ0gcSc:7_cXc.7ucn1eb5dp04dsaT7@1jc$dt4+b.a/be1jbgc`9Uc.bka@c#dKdM3EbB82dldbdH01dedrdgcv9.0V0B0r8p1h219@cw9`0u1A0#9r1AdicAcGc?d.dcdSc1c}bsd64o7^a_eh3kdqd)2+bBccb/a:bGdYa{bKajcCanapdwd/9Bc2eg59az9w7Wc48+87el3yaKaMaOcu0:aR0X0vcZdOdDeO3UdTepd$d,b~eDc|brcTd/a;b,ejc4bJa}cTeqcK1jb6eveicWe#b-c)dR4ac,e 2lc9f281ez9LeFe`d$ekd25?b`fbb1e|cfb,bJcke/d/debUcsbX1be7dke+c^aEdUd3f4esdV04b?b^f8bxbzdCd93Qdmbpeffgc!fidN5{fafjb0bCfocgfIcDcjey8efu9hbS9kfxdhcxb!cBfCaYeodxfJf*fFfkdFfd3H8a0$1=eGf+c(f~e:e}d(fo9p0hg1aec0dwbBfR1kfTcD1jc_f5bbeee.dCfYd*f}dC0Mgp06eb8yde0!d?fAf{aldbdn8#fNe$04drcKdvcOdzdBfme!f$c{dLfoe~gvemg)g#dQgb9LeCet04dXg,fOc/g/ggg#e*gOebf:9)d=9,d^d`d|0!d~2Y0!e1e3e51Bf`e9dah29vfUgyg#gAe(fGgVg#erg2c+eug`bIf-bMd-hmfGgdg@0Fgkf 6:f#ead/aa12acdKffayaA4o8aeKf2eMc47(7*dAeSaQ2{eW6?cUd0g$fZg(gne)gF8Dc0hTgS01e;h|cP1j0j0l0;0o1rdA0ldC0Dhqh.ewe_gDbnh|dJh|b9f29Bg?fJg_g;c8d!dCigh1h`fVgzdEfPhuf)fqhBclf/gIf;bTbVfybZczfBiv6+b*fEglaYincefL8rh|flg%h/h^c@hnc~i#d7d1h;dZ4PgDiCh|frf.8.h3f=crctcvf_iNgNhNc0hGg0c-8wg5a91jg82og~hzh}gfh d4gh9mhJe,fHgBc!i%b iQgtiShKc(h{i+f004ibj3gDjqa7iwhojybujAh#jiihjgje9Bj4jpdKiV5?f7jehMhwcV04gpjmf~e{jNfph cQi2i4i60ni8g#iae@iEfWeZ0Miuiq3-iijPcQ2Ii9hDjFi)gajoeZjBgCj*g+j~4hjMjeb}jPe%jvhxg^j6g|ki1jj$jCiBe+greZj}hkjrhFfohIkp7pgGecaBaohQaqjhgxi*4ueIiQ9B0Q2Q0BeLaHjI3y9B2V7;aO2vkXdxf20,k#1F3/0;hS0Y1F2#1chUeJaDk*eNkZ3UaK0=k?2K7-j00g1Qj?jLjnhrkyjEj3a+3nk$i=kkaLh(aPeUh+eXk4ilkld+j8kJeBgY1j1Tlrk f37Fk@1Pl8lCiklCi0cR0i8@lBi.kglbkm9PkoiZisg g:jZed3a0}lhi4itkz4L0d7Q7x1$3b1R7z1R0;7Bl@2=2-0na-7y7J1Xic4ocz0X0Q0n0,0o0X0:0z1j1J1La017gp1$3u0:a20}0u1ecF0#0o0J0jawi48R3/mr0Vmu1y8^ml3u2 3H271^1`1|m22l2H2p2r1j2N0@bq0!cv0Ei30:1A7O7L3^3e7Nl.mM89aCju8yh!ileQcul5djj1k9f%aWlQgwh?c!h0j2js9xjTjjfMjXg4g#jEh_n3lxi?j_lvhW8ZgRlk9NihgXj,8=lNj`m{iz90dClZiTfGm ldk5iH9)a2gi9*9l9qdwkHkBangukfm~fo9JkNnmjea;jl8yi!m}jJnbi(9%iInHh69/0(9;0o9?2Y9_9{9}22a09ka4nKgHndkLjUb)ngf|gskK8JkMjee^awcTkRo4hYlCm:lKaKff0XmBl)l9ls041_7/omlIc;nh2lhPo6o0j!kbfG7+m@e8lPm`g(0}itfqnjhjnyc(oJnngtoz4+gZnroGlc9Loqlig hvl,m*l:l/0d7zm10.0m0V0=000n0%2V9*009.222f0n0u0r2%0}e61+2#2%222Y1a9*0/2n0i2Vp30i0emjm10_12i40V0(7;2Ue69,2Ii49`2pa30Q0Qa4d~7F1y9*0r183K0#d{cw0Y9?7P7GaLm?hi0D0iigm*gL0u2y17d~0!0}9~11170#fz2YpO7R8MpWaO8K172Y0jpM191P0e0V0^0no;l3p81P2u1ybZpM0g87m*oQpW3K1a0icv2Y0y0/2Q0V0{0r0=1N000?0Vpao!pn9,l%2S0g13qg0opi1(mkmmmo8zl6msppl7pg0Jp00Jff1j2Pdj0I9~qMpr2XpGh{mEm10vqk8cb#0V0%0m0Y0j3K1K2pcv1nq9o|0Vo~0i0#eU0V0Dp-6+1r2V0:1qi40c1j090D0G09l+3Mqs8yr52ir80ora04rc0irf3Z0s9`0nppe4d^p_1B3K0%3/r62K9`0#i}cw1x17aD2np+mzn_n;k?mun/8U170g0/2S0irWqt0Yp+210=p}0_rJ0xq0p#a+q~1hp8q#fVqE1)7I304amI291{2C6:mO2J2LmSmUmWmYm!8_m$3f8_o)n3oen!25ogskl0h%aNlnaRoXm+gTnAf%n1kAjmjxnPb;hysC25e?k,atiekvnVjOsFb|f1lKklgelVn8i:g ov3ye-kPoHh/oBg3iAotf(j*nXiQo2i_nDf=fwrJi m^oNgqkInin4kNoTf68nb@iYsV04bAd$n$hEjwixhpnud#c!o%lTj sEl!ewfscms=cqiKf^fzhisYbIoMjdsOh}nok1nqlOonlCcYnwn5j*iptm4ojYoYj!syfSn%nNjusAtds+s(cIjDk5ncn(9)gKbXl6t%s}owtykNhtnVtCtAlLdAoWtGsn01tIf2k0t~jQtJt0kDkFu5lkj(h@t.nM5{d;t+dhh7d{1ghaq3e09*hf36hht-kwd.jGs#tQs%lat?t~cbljtAi@hCo3eAn hStY5Xl-pPo*l 0(3u1Ypl2b22qYpggLqs1E0/1_3/7;pLn:n/0c0VdA9;1Amhpj051w3u1_1Zl.mH1`s1mLgQs{j%gWoSlylMtFs+m|s$4au0s+nxtjlRt1b4dWu8g miuO7R0V1He62S8KdApoq*2nu*qq15bV0l9{u/7:2X9^pMpp9|0Vqs7Fq vA0r2y2@rja+rlaNrnrb0D0!0A0H1Ct49rrs4S0ev.1Ru{1lu{p.223-s0mKs3andot=jRjVt^tN3koVv9uCsQt~vet~u2vcgwubc!vgjmvjsDsUtAtPsuc5d%kNwfnB8_vp7xvr0Vvtn/cvlE2Kq~u*rim*0!0td5qdpG1_n/d v@90wJ1Rm*9`r*gMl7d_ukd}q41Aqh0/0{qs0/0;0/2uq 0/r+v:0}3u0du_1lml0Vmn1e110r0c7:2K0JuY1A1j0|u-0}0I2Kpopqpg1Rq%r}u~28v{wos5mQ2M0VmTa+mV2Osbgnse7NsguPsik|hZkYu3eQlmeTeVlqt}wdg-swtRlek7e/g@s.fXj^a|oai;kde=w8xNsZlSsTtMoOf!lXs+rgnLtXjHw7jKf2nZx(sPs,sMj+o8s:b/i`iJf@i~tuutiPo4nOw3x)wj25b=t4kpt8jSuutbfeuMx|wpt!irsWs+tisTxVciaiuHs;9fn)i|iLwXtwf3w0knyyx.j7uIb)jag9xTkcx keydgTyKlUgiyMh=fQnCn3ycx-g(sByqsHsRg.yvta8Etqdft,s`udhOt;lkuByXtBv6npv8nsj!vbuylRwsknyWzaweu9t_sShHvmvftzy/ouymk6t)f=h5ui1Bh8ulhb22hdupq~hgyHzqkxyox@zox_y;z1zfjJywxUiDyAiFh1t(gckDy$i/kqn2o4nelky.o(uP1(l;o,m01!04p cy340#1hq=9*8c0Qqk2pmz9,n_pap_p1d~34i48Lv^q2wEvNd/rkr7vYrorcv$0Hv,3dpw1BrNpBq4zxw#iM0/0#0/11qgp@22vVrFAiv!0!Anb/w%pbw*0Vw,w.mf0rw;2u1pAbk/0=w;r{uT040krB9{q/wYczha0nAyqtq0A5p{a30cA92{cw1r9-A`A=d~wQjbegpW1N0}o;o?2!0ppn1NvTAfvWAhr9AHv%AJ9EaNi4A8A:qtl%k$BeAFBhrppTBk2+A!w{qH1ex60i0JmZl70J3a0Y0%dAAV0Jr#c.0vxfe6BHiMBLBNxd0W0@0.xh0+A#0v0Y0}z_9 1O0mmg9{cup1q4vuq9u$u(2#q9A0u)qtv^r`u@1#l%0%A)0;1e0a2t3-0;0$1K0Y0{byo;0g0#1;2b0!0=0~0dl-0uph0{0=111_0(0g0e2{0;0d1@0d0{110#m80u2-Cf0BCh0}0K0+0O0e0+0e0G0d24120=1S0(0%0d0H0w0n0G0e0=C(2t1g0;211e0~0$1rpelN0~010d3Mo/0Vm6pE7F0i2q2V9~0mo{1g1_0=aNuZp)q|t{vQ177`1K040=1_mr1RDp0s9{rxxv2i1ABAxjv_u xm8yxo2KmRxrs9DzmZxxl;sf3fshodxDofxFyqh$llsqxJlph-bBz9woimitxRfGz*vhvky0t_j-i3i52!j;i9ysa9sJxZhurgsTzeD;jJD*gmu7lWyux^x;zWzIuxwoy:w9c.ykj{uEz2uGzUy3y_s@yGtvyPg6jttKx iXyjy(zquwk8zOsGi-yqwnj)x zZtni^EsyDnEtsy7iMy|Exl#Eoy,z!7ux=9wB2yTkCx#wrn6gjEAx^y@fDuLzJEIx}D~zbt$zGt/x)D:bBE}zgu1sNDYkhE?layfdIvlEbz#zKmiyUx^zQj5z5j.D`i7D}xXexyBFlE3g@E5eDk22pstEGz7uzoozclUE5kus+FjnzEat6tgeZFNzXE2y)E-x kEFgkGEfEyo5hRkND:1lwv7vz.o-u^0mu`w@0L1Bp_1w0/px7w0i2@0ji5p1pMgKhc1aA11BmXDAhhq8BpBcqg2Vw.0u0034cFr8pg17vBo:qzi4p}F^22Dfpnp^0YF{2p17A.mrqg1OD4k:q?qg18a4Ar0;p}A%9-Den.A)3/17wQFpD{j=B40rB68!q~2WA`rnA.i4wDwBq2A}Gw9;pvd_1417r$u%0/G:G|ALDjq@b#G|9?d^r(i4q^n/21G:rvwM7:pGG6qoHhwYB_A}o;Hca3Gg7;p}D3vEq0d^0%141Bqyk:2ycvpx0BG B+2#hezDpxG/Cp0V0Sw?F?A$1BA,G7GwA;p`A7qCAaA{q`A`0npz2$132Wo`q{q}vQH(G?n?2fo}DleUqEv;1Rw`z;D3k^pn3KGWH^9|H`8f2f1A0%04rA2{2)IclN3MB{p3h(uZqs2K2b9~F}HXDC1YGR0!wApH0mpJ21q9v@xkmJ2av|8:1jk3xME{lDypIPEjF9y=wbF8IPu4naFcFPwmx/FbFHif7OF-HrGIG*DiADm*p:pPa3qhI=pPwKI^1HrQG%AOn-pnd^2xClq8ACGMuWDk2yvQr,rJqs0(pMJ9Ic0rqMBpGmd{22HRqFm10EGdp6eUClJyHr7FDb002R1g7/Dg2W9`1q9;n?z@u.Gjd^u}haqor%8K0u9`vtq8vwa*F|H)G@cu9^22CP0uu%9;HEB.Gwq4360BrU17qy14l7GQ1BpAvwpCfVz|p6G/q@o;9?mrJbGxn^J1F~2@x0u.8!JMCP34J9A-mzI rJ9|1cB6KiGIJMJTrX0np$11Iw1ZC6C8CaCc4aCeCgCi2t0=ClCn0;CpCrCtCvCx0oCzCBCDCF0:CHCJCLCNKMCRCTCVCXCZ1cC#C%C)C+C-C/C;q|2VC^01C`C|340%C D10VIyGCaMr%wYp9q00%0/0iqkDhp4J@rTk^wX17u#0{pMA90Vv(vMJ.0j1yp}0 AqH,0;9`vCy6A{17J-J/AY9*pZC1rMHswYJ|p%w=Jtz;uVpnJFBrJIuZptG{AY22qsC?p(bW0c7;z_mrv.DCw|w~01120J1a0J1nk$1j0 cvpaM0pn0CB%A#Hvn?vwd^I9ItL:ClB,zAGdo~0(140mIEK9q9K3e.Hp0%G:0/KE0.J.220~D4J}22JRK4q_H^H=r0r36:AgrmAj0D0nByrhBtvXBvrc0jMUu+q`GT8Uq9Kmr#d HHKmHKw}J.q=G:J=q|LsK}2pA`pYM,paM.HJv^A.r0B5gLCDK7GLKzu/KBmnKeHYd_HIp%uX1,qD0VLBM60oJYHB0;qW22MJp=i4p!q4MLq4JQ2XAxG4o@q3LQ1gpqqmqoqqrir4BfMQv!rrrgDCo,12Mo0=04.