Carré parfait

Soit $n$ un entier positif ou nul. $n$ est un carré parfait s'il existe un entier $p$ tel que $p^2=n$.

Il est facile de tester si $n$ est un carré parfait : il suffit de calculer $\sqrt{n}$ et de vérifier si cette valeur est un entier. Mais... on interdit dans cet exercice de calculer la racine carrée d'un nombre !

Pas de racine carrée (ni de math)

Il est interdit d'utiliser la racine carrée dans cet exercice. Afin de limiter son utilisation, il est interdit d'importer le module math.

Une autre approche consiste à énumérer tous les entiers positifs $p$ dont le carré est à inférieur ou égal à $n$, à les élever au carré et vérifier que l'on a $p^2=n$ :

si oui, $n$ est un carré parfait ;
sinon, on passe à l'entier suivant.

Si l'on a atteint un $p$ tel que $p^2>n$, il est inutile de continuer : $n$ n'est pas un carré parfait.

Vérification « simple »

def est_carre_parfait(n):
    p = 0
    while p*p <= n:
        if p*p == n:
            return True
        else:
            p = p + 1
    return False

Cette méthode est valide mais elle prend du temps : tester si $1\,000\,000\,000$ est un carré parfait demande de tester $\sqrt{1\,000\,000\,000}\approx 31\,623$ valeurs...

Une dernière approche, plus efficace, utilise la recherche dichotomique. En effet, si $n$ est un carré parfait sa racine carrée est comprise entre $0$ et $n$. La zone de recherche est donc définie. Il reste à tester la valeur centrale et à continuer (ou pas) la recherche en conséquence.

Avec cette méthode, tester si $1\,000\,000\,000$ est un carré parfait ne demande de tester qu'une trentaine de valeurs ! En effet $1\,000\,000\,000 \approx 2^{30}$.

Écrire la fonction est_carre_parfait qui prend en paramètre un entier positif n et renvoie le booléen indiquant si c'est un carré parfait ou non.

Contraintes

Il est interdit d'utiliser la fonction racine carrée.

De plus les valeurs des tests secrets sont très grandes ($n > 10^{18}$). Une recherche linéaire sera trop lente.

Exemple

>>> est_carre_parfait(0)
True
>>> est_carre_parfait(1)
True
>>> est_carre_parfait(2)
False
>>> est_carre_parfait(3)
False
>>> est_carre_parfait(4)
True
>>> est_carre_parfait(15241383936)
True

Version itérative videVersion itérative à compléter Version récursive videVersion récursive à compléter

Évaluations restantes : 10/10

.128013:ag)1iTkn9/S=vFmsuhb84;y7e6+2*o-dt c0(wr5_P3plf050H0A0I0c0g0U0r0J0K0U0c0r0r0n010I0g0T010406050r0s0q0q0c0O0y040m0F0U0s0:0F0j050l0`0|0~100^0T04191g051j0l1j1l1g0^0H0g0o0(0*0,0.0t0g0d0t0U1z0t0I0?050Z0u0U0A1u0+0-011y1A1C1A0I1I1K1G0I0u0F0H101H0O1h0I0t0(130r0T0c0j0.0D011M1w010V0#0A0j0c0q0A1G1.1:1^1O1{1K1~200?0a0J0R0O0F0T0F0r0g160j0J0X1,0O0O0A0K2l19230j1h0l1*2y0I1(1%1)0H250.1C0j1}2i1G1r1t0)1N2I0g2K0j1!1s1G0T2r1h2w2y2$0_1/2m2Q1_2V0O0}0U0?0J0f2v2*0@2)242,1O2.2:2=0D2^1:2`2w2H012 0c2;040J0S332x0^362}0.393b0J0w3f352*373l2=0P3p3h3r3j380F2/3a2=0B3w2{2+1v2~3B303c0z3G3i3J3k3L3D3c0v3P3y3R3A3C3m0k3X2|3Z3t040f0L3(3I2R3!3M0f2@1a2_3x3)3;3+0f323_343{3:2-3T3b0f3e413g3H3s460?0f3o4a3q3|453#4f3v4i434d4m3,3F4i1i2!192O2B0H2F370K1!211h4z1k4x2(4v4E0X2#3Y3;0i0?0X0V3p4c3z0N2=4W3Q3}0V0?0A0r0I0Q0K0~2r0Q1/0O0V0!0I4#4Q1_0=040M4`4k2~0?184v4$4|0?0e0b3w0J5c0J4X3*4T0A0u153p5e561O0F0?0n5l5f3;0q0g0?3.4p5d5m4{52041{542$5B510.5p045r4i5I445D5G3`065A5t1_4S040N1y1K5s5n3k5h5j4_5O5W5o0?020U0I0x5N5H5.5)5E2T505Q0.4}5a5z5A5d5`380?5v1C0A0s5%5C5K5q6d5J014}4 556e67040X5+6h5 015L0C6s3s0?5F5~374}0e6x3z5L0l0l6F3Z5v0?402$5U645c660j680#0g6b4-4/0A6K3;5L5^2_5P6y04696X6c5-5(6u0?0E6$2-6V6a6:6P6Q6R665Y0g4V6;6n6U6-6W6Y4.2q6#756i5L5;5?6_5R6B3z615b6R646T5*5k7e6t6(7j5{6.6b7x6?046w7u376M3,7o706=5Y0A1C745_6=777z0s6Z7c7B6(6)346+3z775S34667n637p657L0?2r0I0s0O7(2x7#3Z0i0K0?0h0O0s7d6P7-714)0$822_7*0?62837-7.766z5}7F6G6g8j5g786|7X0?0G7B7H3^6~5V7/047;7?7^3c717}040p3a0r8842194N0A2y2Z8O4y1s4A2B2D2z1Z1#2B0c1J8R0l4z0^8(0Y0!0$04.

Évaluations restantes : 10/10

.128013:ag)1iTkn9/S=vFmsuhb84;y7e6+2*o-dt c0(wr5_P3plf050H0A0I0c0g0U0r0J0K0U0c0r0r0n010I0g0T010406050r0s0q0q0c0O0y040m0F0U0s0:0F0j050l0`0|0~100^0T04191g051j0l1j1l1g0^0H0g0o0(0*0,0.0t0g0d0t0U1z0t0I0?050Z0u0U0A1u0+0-011y1A1C1A0I1I1K1G0I0u0F0H101H0O1h0I0t0(130r0T0c0j0.0D011M1w010V0#0A0j0c0q0A1G1.1:1^1O1{1K1~200?0a0J0R0O0F0T0F0r0g160j0J0X1,0O0O0A0K2l19230j1h0l1*2y0I1(1%1)0H250.1C0j1}2i1G1r1t0)1N2I0g2K0j1!1s1G0T2r1h2w2y2$0_1/2m2Q1_2V0O0}0U0?0J0f2v2*0@2)242,1O2.2:2=0D2^1:2`2w2H012 0c2;040J0S332x0^362}0.393b0J0w3f352*373l2=0P3p3h3r3j380F2/3a2=0B3w2{2+1v2~3B303c0z3G3i3J3k3L3D3c0v3P3y3R3A3C3m0k3X2|3Z3t040f0L3(3I2R3!3M0f2@1a2_3x3)3;3+0f323_343{3:2-3T3b0f3e413g3H3s460?0f3o4a3q3|453#4f3v4i434d4m3,3F4i1i2!192O2B0H2F370K1!211h4z1k4x2(4v4E0X2#3Y3;0i0?0X0V3p4c3z0N2=4W3Q3}0V0?0A0r0I0Q0K0~2r0Q1/0O0V0!0I4#4Q1_0=040M4`4k2~0?184v4$4|0?0e0b3w0J5c0J4X3*4T0A0u153p5e561O0F0?0n5l5f3;0q0g0?3.4p5d5m4{52041{542$5B510.5p045r4i5I445D5G3`065A5t1_4S040N1y1K5s5n3k5h5j4_5O5W5o0?020U0I0x5N5H5.5)5E2T505Q0.4}5a5z5A5d5`380?5v1C0A0s5%5C5K5q6d5J014}4 556e67040X5+6h5 015L0C6s3s0?5F5~374}0e6x3z5L0l0l6F3Z5v0?402$5U645c660j680#0g6b4-4/0A6K3;5L5^2_5P6y04696X6c5-5(6u0?0E6$2-6V6a6:6P6Q6R665Y0g4V6;6n6U6-6W6Y4.2q6#756i5L5;5?6_5R6B3z615b6R646T5*5k7e6t6(7j5{6.6b7x6?046w7u376M3,7o706=5Y0A1C745_6=777z0s6Z7c7B6(6)346+3z775S34667n637p657L0?2r0I0s0O7(2x7#3Z0i0K0?0h0O0s7d6P7-714)0$822_7*0?62837-7.766z5}7F6G6g8j5g786|7X0?0G7B7H3^6~5V7/047;7?7^3c717}040p3a0r8842194N0A2y2Z8O4y1s4A2B2D2z1Z1#2B0c1J8R0l4z0^8(0Y0!0$04.

Évaluations restantes : 10/10

.128013:,ag)1iTkn9/S=vFmsuhb84;y7e6+2*o-dt c0(wr5_P3plf050I0B0J0d0h0V0s0K0L0V0d0s0s0o010J0h0U010406050s0t0r0r0d0P0z040n0G0V0t0;0G0k050m0{0}0 110_0U041a1h051k0m1k1m1h0_0I0h0p0)0+0-0/0u0h0e0u0V1A0u0J0@050!0v0V0B1v0,0.011z1B1D1B0J1J1L1H0J0v0G0I111I0P1i0J0u0)140s0U0d0k0/0E011N1x010W0$0B0k0d0r0B1H1/1;1_1P1|1L1 210@0a0K0S0P0G0U0G0s0h170k0K0Y1-0P0P0B0L2m1a240k1i0m1+2z0J1)1(1*0I260/1D0k1~2j1H1s1u0*1O2J0h2L0k1#1t1H0U2s1i2x2z2%0`1:2n2R1`2W0P0~0V0@0K0g2w2+0^2*252-1P2/2;2?0E2_1;2{2x2I01300d2=040K0T342y0_372~0/3a3c0K0x3g362+383m2?0Q3q3i3s3k390G2:3b2?0C3x2|2,1w2 3C313d0A3H3j3K3l3M3E3d0w3Q3z3S3B3D3n0l3Y2}3!3u040g0M3)3J2S3#3N0g2^1b2`3y3*3=3,0g333`353|3;2.3U3c0g3f423h3I3t470@0g3p4b3r3}463$4g3w4j444e4n3-3G4j1j2#1a2P2C0I2G380L1#221i4A1l4y2)4w4F0Y2$3Z3=0j0@0Y0W3q4d3A0O2?4X3R3~0W0@0B0s0J0R0L0 2s0R1:0P0W0#0J4$4R1`0?040N4{4l2 0@194w4%4}0@0f0b3x0K5d0K4Y3!4T044V51451P4!3d5l3t4)042s0L5q3A4~50564|535j0B0v165w3!4~0c3q5f575C1|552)5N0/4~5a5c5e5X5g4S0@0h4W4j5M5B3l4U5E5G5(5Z1`0G0@020e0J0y5L5:5O2U5H3=4~5b4q5X645e5|0/5i2s0J0t0P5Q2`5)52680L0@0q3b0s0B3x06655d67390@0r0$0h0B0t5{5S015=040o6B5*015y5 2.5,5F4`5/6C6E0D6H6h6u045P6L1P5U6U5m0/6E0m0m6$386w0@412%6q6r6t0k6v6x6z4.4:6o6Q6I6E6G6 6V6^046w1D6z6,3A6E0F7a3+6_786A4q6=656t5i5$7e3~7g6y0t6|2r6~2%6g6%6D5?0V5_7p6M046e356t615W6r666C690Z6c7H2y7y3t0@5u6Z5T0@5z5R6I75777s7E1P6S7+0/6.3-7Y6J0@5K737z756Y5A6V6#636?7O4*1D5%7x6@7r6{4/7v7.7A6F72866C757S4Q7~0@626;7M5Y825t7Q6d8c0j6j040i0P0t7w3{7M7m836n7=7K808p7U3A7P6b8u7_7V8s5v7}7z6K8V8S0Y6O8I7@8c7(6`7i8g700@0H8c7:3_7$8l040f6p8q6I8O7R8(7W2t8$4 7=7:3/8Y5x8%8R3A8i928_4q1a4O0B2z2!9i4z1t4B2C2E2A1!1$2C0d1K9l0m4A0_9y0Z0#0%04.

Évaluations restantes : 10/10

.128013:,ag)1iTkn9/S=vFmsuhb84;y7e6+2*o-dt c0(wr5_P3plf050I0B0J0d0h0V0s0K0L0V0d0s0s0o010J0h0U010406050s0t0r0r0d0P0z040n0G0V0t0;0G0k050m0{0}0 110_0U041a1h051k0m1k1m1h0_0I0h0p0)0+0-0/0u0h0e0u0V1A0u0J0@050!0v0V0B1v0,0.011z1B1D1B0J1J1L1H0J0v0G0I111I0P1i0J0u0)140s0U0d0k0/0E011N1x010W0$0B0k0d0r0B1H1/1;1_1P1|1L1 210@0a0K0S0P0G0U0G0s0h170k0K0Y1-0P0P0B0L2m1a240k1i0m1+2z0J1)1(1*0I260/1D0k1~2j1H1s1u0*1O2J0h2L0k1#1t1H0U2s1i2x2z2%0`1:2n2R1`2W0P0~0V0@0K0g2w2+0^2*252-1P2/2;2?0E2_1;2{2x2I01300d2=040K0T342y0_372~0/3a3c0K0x3g362+383m2?0Q3q3i3s3k390G2:3b2?0C3x2|2,1w2 3C313d0A3H3j3K3l3M3E3d0w3Q3z3S3B3D3n0l3Y2}3!3u040g0M3)3J2S3#3N0g2^1b2`3y3*3=3,0g333`353|3;2.3U3c0g3f423h3I3t470@0g3p4b3r3}463$4g3w4j444e4n3-3G4j1j2#1a2P2C0I2G380L1#221i4A1l4y2)4w4F0Y2$3Z3=0j0@0Y0W3q4d3A0O2?4X3R3~0W0@0B0s0J0R0L0 2s0R1:0P0W0#0J4$4R1`0?040N4{4l2 0@194w4%4}0@0f0b3x0K5d0K4Y3!4T044V51451P4!3d5l3t4)042s0L5q3A4~50564|535j0B0v165w3!4~0c3q5f575C1|552)5N0/4~5a5c5e5X5g4S0@0h4W4j5M5B3l4U5E5G5(5Z1`0G0@020e0J0y5L5:5O2U5H3=4~5b4q5X645e5|0/5i2s0J0t0P5Q2`5)52680L0@0q3b0s0B3x06655d67390@0r0$0h0B0t5{5S015=040o6B5*015y5 2.5,5F4`5/6C6E0D6H6h6u045P6L1P5U6U5m0/6E0m0m6$386w0@412%6q6r6t0k6v6x6z4.4:6o6Q6I6E6G6 6V6^046w1D6z6,3A6E0F7a3+6_786A4q6=656t5i5$7e3~7g6y0t6|2r6~2%6g6%6D5?0V5_7p6M046e356t615W6r666C690Z6c7H2y7y3t0@5u6Z5T0@5z5R6I75777s7E1P6S7+0/6.3-7Y6J0@5K737z756Y5A6V6#636?7O4*1D5%7x6@7r6{4/7v7.7A6F72866C757S4Q7~0@626;7M5Y825t7Q6d8c0j6j040i0P0t7w3{7M7m836n7=7K808p7U3A7P6b8u7_7V8s5v7}7z6K8V8S0Y6O8I7@8c7(6`7i8g700@0H8c7:3_7$8l040f6p8q6I8O7R8(7W2t8$4 7=7:3/8Y5x8%8R3A8i928_4q1a4O0B2z2!9i4z1t4B2C2E2A1!1$2C0d1K9l0m4A0_9y0Z0#0%04.