Décomposition en facteurs premiers - v2

Le cadre

Afin d'améliorer notre précédente fonction de factorisation, on souhaite une sortie sous la forme d'une liste de tuple (p, e) où p est un nombre premier et e l'exposant non nul associé. Les tuples seront donnés avec p strictement croissant.

🐍 Script Python

assert factorisation_v2(7) == [(7, 1)]
assert factorisation_v2(8) == [(2, 3)]
assert factorisation_v2(9) == [(3, 2)]
assert factorisation_v2(10) == [(2, 1), (5, 1)]
assert factorisation_v2(11) == [(11, 1)]
assert factorisation_v2(12) == [(2, 2), (3, 1)]
assert factorisation_v2(4953851) == [(7, 2), (17, 1), (19, 1), (313, 1)]

Cette sortie est plus proche d'une écriture comme $12 = 2^2 × 3$.

Exercice

Coder une fonction factorisation_v2 :

qui prend en paramètre un entier naturel non nul n
et qui renvoie la décomposition en facteurs premiers de n sous la forme d'une liste de tuples (facteur premier, exposant).

La liste sera donnée dans l'ordre strictement croissant des facteurs premiers. Les exposants associés seront non nuls.

On pourra se contenter, ici, d'une complexité linéaire en n.

Évaluations restantes : ∞/∞

.128077.128013x/.r;nbOylae%u)d63m(P+02è-@],59fÉq!7}8 _o={pcwgv41kRIéhtsSàLC[Dji:050r0n0)0m0=0l0*0O0U0l0m0*0*0R010)0=0T010406050*0p0u0u0m0f0k040+0Q0l0p170Q0h0O020m0u0T0g0O0#0n1h0f0J0p0n0*050d1e1g1i1k1c0T04051P1I1S0d1P1c0r0=0X0 1113150(0=0W0(0l1*0(0)1a050`0i0l0n1#1214011)1+1-1+0)1?1^1;0)0f1Q0)0(1`1%010H0|0n0h1v0n010 1n0*0T0m0h150z1;2n2p2b1|2e1^2h0u2j040b0O0w0f0Q0T0Q0*0=1q1s0^2l0f0f0n0U2N1I2u0h1Q0d292Z2628271=0r2w151-0h2g2K1;1Y1!101{2-0=2/0h0Q2?1;0T2S1Q2X2Z341d2o1s2^2c2}0f1h0l1a0O0Z2W381b372v3a1|3c3e3g0z3j2p3l2X2,013q0m3f040O0t3u2Y1c3x3o153A3C0O0Y3G3w383y3M3g0F3Q3I3S3K3z0Q3d3B3g0s3X3m391$3p3$3r3D0L3+3J3.3L3:3(3D0N3@3Z3_3#3%3N0G3 3n413U040Z0y463-2_423;0Z3i1J3k3Y474f490Z3t4k3v4m4e3b3{3C0Z3F4s3H3,3T4x1a0Z3P4B2Z310n2Z2?2$0r282+3!0U2~2C0@1Z1Q4L333k3Q054U0^4#4n2c0!1a0^0H4%3^4f0V3g4=404o0H1a0H0m2U3$0=0*0m2N0P0X4r364?2c19040v4`4,3p1a0h5g4v1|5d0q0?3X0O5s0O4D3!4.041{0n0f0)3Q5u5b5i045k4J5E4{2c0Q1a020W0)0g5D5v410u0=1a4c4J065t5K5h3L4~500)0n0p0f1H5J5U4f5N040R5T5F155d0/0D5r5t5=3b1a0T5`5L1|5@5_5;5{015W1a594l5$621|5x0V1)1^665(3z5j6p5m155@5P5R6t3y6e4a5l3y5d5q5!5$6i6c0h1a0n6z3!696O5V5X045Z345#6I5s6j156l6n6N6b675)5H6R5?1a0o6-6304656)6q696a345%6u6d6T6V4$6c6F606Y6J6*6r6,6^6~5@0d0d6{3k6}3T6475766Z6K6M6;681a0x7g3v7i3!6B4j6W7m6!015x0=4;7b7j046(6|7C6w5Q5S7H7x706D3!746H7m617o044 2U5-5/7T415@0e7)4o1a0m0T0T2g0r7-5c1a0v5f4J7C6L6?7^5n1a0E7q6+7K72785o0q7l776q7 6@7L6c5@7t856 4G3X6X7n785x2S0)5.5I8h787 7#5,5.5:6W1I4)4M1T321I4O1I0)4Q8M2)2!0m1@8H0d4O1O4+6~2S0u0P4 0!0n0P0(0t1a1A1C1E1G0O6G361V3l2?3y0m0r0u1r2M0=1r0O2{0H5@1O8{8}8 2N0B170)24040I8u2P2P112l1w1^0c2M0%1T3l1P0:2p0~1^0O0T0=2S0O0^0~0U120O0v1E2p2+7C1i2M0(1h5,0c1a090v0h098b5J1G0)0O0p1s2}0u0i9C4L5W5A0q0E0O9l9.0=0A9C0i0Q0p101_4(4V3y1~1,1.1:8Y3y6$2f4%0d8G3D4 2M9z2S0*8:7w419O299R0n9T049V9X9Z6|0)9}5/9I9l9|9~9ya12P3!a4201/2t8r1a6mab7}ad4V3D2{5,0f2/0OaYag540h9$0m9~9(0Oay5.0q7,8^8X9v0h9x8;9Ga^0~0T1o0~4 0X3$8S1^0~9J0p9Lam4fao9Q55ar9U9W9Y5D9#0O955B1B2g9$4U1w2K0%9;9?0mai1B9_9{9}9 5u8Ga31.aKa77Caa6oaRae9z5A2B9$2P0f0%0r0p9B1_4Ua@0=0r0%0fb3bna%bDaT5Iae9=0;0pak0p000,3ha:1W1R040j2Oah3B3$0~al0l003B0W52ap1_bj2gb92cbbaqas9V099R0(9G0l0S0j0M9W0qbh4J9=9}0O1E000|0Obj2.0%0{9Cce9N0f9Pcibfav3Q9=0r9w9?1_9A9C9E0 120e0O0-bw2}0`2Ncf1|chbdcj0vcl55cn3B0O0jcv6|0*cBa%b%1G0*a00*261r0W5y0p9zbX9Da_122Wd50hd70O0K9s8X050=0u0W0O3B0)150a2k3!0)0V1B0Q0;5X0O0*0f0U1(220T0*0?7e0U0r0h0e0;0*0^1-0X0f0e2/0)0d1+0d0;0^0U8(0r2!dz8~dC0C0Z0F0e0Z0e0y0d5z0)0*1J0X0W0d0Z0H0Y0Y0r0e0*e02k9d1^150?0x0Z0?010d3D0$0lcDd49z2K2L8T9D000Q0i5,0h9B9%aYbqa}ar9q0Ob(0U2{cH1_0m0X2Tdc0O2B0hb=drb;d4b*d}c#0.1_d2b(eq5.bv0O0X0tb{3l8V4Y1c8V0_0{0}04.