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
L'objectif de l'exercice est d'améliorer la fonction >>> limite = 20
>>> primalite = eratosthene(limite)
>>> primalite_brute = [est_premier(i) for i in range(limite + 1)]
>>> primalite == primalite_brute
True
eratosthene en suivant les conseils suivants :
- Remplacer la ligne
for p in range(2, n + 1):par une structure avec une bouclewhile. - Remplacer la ligne
for kp in range(2*p, n + 1, p):parfor 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\). - 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
whileen conséquence. - Tester votre fonction
eratosthene_V2en la confrontant àeratostheneet à 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.
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
.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.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)