Aller au contenu

Test de primalité v2

Le cadre

On souhaite améliorer l'algorithme naïf avec l'idée abordée précédemment.

Pour \(n > 2\), si on n'a pas trouvé de diviseur dans l'intervalle \([2 ; \sqrt{n}]\), alors \(n\) est premier.

👍 En pratique, on pourra obtenir en très peu de temps des nombres premiers à 10 chiffres.

🐍 Console Python
>>> [p for p in range(10**9, 10**9+100) if is_prime_v2(p)]
[1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093, 1000000097]

Exercice

Coder une fonction est_premier_v2 qui prend en paramètre un entier naturel n et qui renvoie un booléen : True si n est premier, False sinon.

⚠ Contrainte : Il faudra coder cette deuxième version (v2) de manière élaborée, n pourra valoir quelques milliards. On ne fera donc pas de boucle qui fait n tours !

###(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 : /
.128077.9888.128013x/.Tr;nbOylaeê%«u)*dM63m(P+02è-@,59fq»!7}8 _o={pcwgvF41kéhtsàSCDji:E050w0p0-0o0@0n0.0T0Z0n0o0.0.0W010-0@0Y010406050.0t0A0A0o0h0m040:0V0n0t1a0V0j050e1h1j1l1n1f0Y04051D1w1G0e1D1f0w0@0$121416180,0@0#0,0n1U0,0-1d050}0k0n0p1P1517011T1V1X1V0-1%1)1#0-0h1E0-0,1+1R010M0 0p0j0o0A0p01121q0.0Y0o0j180F1#2c2e1 1-221)25271d0c0T0C0h0V0Y0V0.0@1t0j0T0{2a0h0h0p0Z2B1w2j0j1E0e1}2O1`1|1{1$0w2l181X0j242y1#1M1O131,2Y0@2!0j0V2(1#0Y2H1E2M2O2_1g2d2C2*202/0h1k0n1d0T0)2L2}1e2|2k2 1-3133350F382e3a2M2X013f0o34040T0z3j2N1f3m3d183p3r0T0(3v3l2}3n3B350K3F3x3H3z3o0V323q350y3M3b2~1Q3e3R3g3s0Q3W3y3Z3A3#3T3s0S3)3O3+3Q3S3C0L3;3c3?3J040)0E3F1H2@1w2(2R0w1|2W3P0Z2:281E461F442{1x39054c0{2^3=2+010*1d0{0M423*4r0!354x4q300M1d0p0.0-0U2?0p0A0@0p0h0U0$3i4k3k3X3n1c040B4C3|4r0j1d1v4U2N4W3P4Y0^3F0T4-3}0k1d2-0-4#3Y4r4Y0u4;4?4r0V1d0H020#0-0i514y304^040k0V1q4|4X1d4:4+1e0T5p4=5c1-4t040@4w5n5r4D3e4)5b5A185404020n595D4$204N1d4T2{5s184/3M5q5W5z5M5t1d2H0-0t0h4*2_5Y4}200*0Z1d0%3q0.0p3M065W525.1d0M3R5L5-5B040w613n0V4A5v5*395,3I5e0h2e0#5^5n5|1-4Y4!6k5S015O045Q4l6q4Y0J663P4(046b4V6w1d0u5m2_5`5X5p6l185u5w6z3}5C5y6N015G0r6R4%4u6Z205G0W0W6$1-6s416p5E015U5n6K6L5{6q5u5$5(6D2N6d3P5/5;5?6j6J6^703?6P5x5+6V6B656U6q5G0v6+3A6#7g6:5G575K7n5Z7l6C5j4.5l5V775q6V6{0|6}7k4s5:040g0h0t75396@784r7D5%5)7G727J7L7N3k1f0e4n0p2O4L2O4g2P481w2S7/0o1(7(451N3a0e0{0}0 0.3a2(3n0o0w0A1u2A0@1u0T2-5 1d1C8284862B0H1a0-1^040;0V0A0Y1)0d2A0+1H3a1D0;0|0-1*0A0+1}4d0T4H0-0T6g0Y0@2E0o0$2I2D4H0T2/0A0k2H116V1l2A0,1k8B0d1d090B0j09505y4c1j1*0t2C4N0n1X1l0w0f8w1f0t0n3a1X040=2e111)0T8M2H8S110Z150J0T140T5g0t131*0M0~8J240$0@2v2C8!0h8$8(0p8*048,090.0N0h0-0X0j0R8/4;0-0V5(112E9m9o9b9R0h2a0j22324P0T0N7M7Q208#1}9B9D8,8.8:5+8I9b2H4N4P0f0T0l2C1M8J3q3R119*1*0.0o2a8q8s8u0T8B8q3R0p8{1*9_249,1-9.8%0o8)8+0B098(0,9g0n0X0l0Rav9H9J9L0R0u9O5n9i9R9)0t00aj9a4H9Z6g0Z2-0~9dan9y9Aas9Cau9?3F8 0e951f950x0~112d0h5 0@0.9i8=270T8P8R9k0$0)9i9k9V9a0.001l0h0q8B8K0o8M0{270j0-a,a.1w928x1E0@0A0#a 5J180b293P0-0!4M0V0?0@290.0h0Z1S1?0Y0.0^0e7$0w0j0f0?0.0{1X0$0h0f2!0-0e1V0e0?0{0Z0*0p0w2PbC85bF0I0)0K0f0)0f0E0e1,0|0.1x0$0#0e0F0y0o0E0f0.c4298k1)180^0!1l0j2-0#0^010e3s8z1?8C8E0,8G5@6gaf0h0G9924be2x5(9005bpa/0@648TcE4O0ha?9{cQ9T1*a#9/a%9;0B0)0SaK5+0Z1T0M0M8Y0TaN8r0ta{1wbn95aN0k4O2~8p2x0.0+11b00Z9j1*c;a?0|2A0T9q2J0p5(9`4McQ0T0/ao18aq9:au0Lc(6cc*5wc-8Tc:1r0.bmcM7#cK1F9698128T9ga{8Hakdb4Paad72D008^0T8`8|0h2W0w002w0+6g2BdK0Z1*9*0@8UaQ4I9b158a0j4I2e0}0j0+a,1KdE05bsbu3q0-180abz3?bBbDbFbHbJbL0-bNbPbRbTbVbX1Nb!b$b(0,b*b,b.b:e9b?0@b^b`b|b~c00-c2ccc50)0M0(0(8~eFce2Acg010^0D0)cocq0T0_dM8Y8Bcz1`cCbfbhd69Y9e8U8p8X4H9i0A0qa~0scAe%0#6g0j0w110O9id,9X160G0{bk0TdT0Yd98Jdc8Bdf4L9|0ha|8pa~cXarat9Ec#0E0)0PeS0Qdr3kaOd-9_2(a`0@7?d;9Zfmdofp0)fv9@39d}7`46.