Nombre premier

Un nombre premier est un entier positif qui admet exactement deux diviseurs entiers et positifs distincts : $1$ et lui-même. Ainsi :

$0$ n'est pas premier car il est divisible par tous les entiers non nuls ;
$1$ n'est pas premier car il n'admet que lui même comme diviseur ;
$2$ est premier car il n'est divisible que par $1$ et $2$ ;
$6$ n'est pas premier car il admet quatre diviseurs : $1$, $2$, $3$ et $6$.

Divisibilité

$a$ est divisible par $b$ si le reste de la division euclidienne de $a$ par $b$ vaut $0$.

Avec Python l'expression a % b est alors évaluée à 0.

Cette définition permet de formuler un test de primalité simple. Considérons un nombre entier positif $n$ :

Si $n$ est strictement inférieur à $2$, il n'est pas premier ;
Sinon, si $n$ est divisible par l'un des entiers compris entre $2$ et $\sqrt{n}$ (inclus l'un et l'autre), alors il n'est pas premier ;
Dans le cas contraire, $n$ est premier.

On demande d'écrire la fonction est_premier qui prend en paramètre un entier $n$ positif ou nul et renvoie True si ce nombre est premier, False dans le cas contraire.

Deux versions, construites autour de boucles for ou while, sont proposées.

Exemples

>>> est_premier(0)
False
>>> est_premier(1)
False
>>> est_premier(2)
True
>>> est_premier(3)
True
>>> est_premier(4)
False
>>> est_premier(31)
True

assert ?

Le mot clé assert est utilisé en Python afin de vérifier que des propositions sont vraies.

Ainsi, l'instruction assert 3 + 5*7 == 38 permet de vérifier que l'expression 3 + 5*7 est bien évaluée à 38.

Si c'est le cas, le programme continue de se dérouler normalement. Dans le cas contraire, le programme est interrompu et une erreur est signalée.

Version avec une boucle for

Une première approche consiste à utiliser une boucle for afin de parcourir tous les diviseurs potentiels de $n$ entre $2$ et $\sqrt{n}$ (inclus l'un et l'autre).

La fonction permettant de calculer la racine carrée d'un nombre positif fait partie du module math. Elle est importée au début de cette version de l'exercice : from math import sqrt.

Attention toutefois, cette fonction renvoie toujours un nombre flottant : sqrt(5) est évalué à environ 2.23606797749979.

On peut néanmoins arrondir ce résultat à l'entier inférieur ou égal en utilisant int : int(sqrt(5)) est évalué à 2.

On rappelle de plus que l'instruction range(5, 12) parcourt les entiers entre 5 (inclus) et 12 (exclu).

Version videVersion à trous

Évaluations restantes : 10/10

.339.8722.1280135q/(ê+0{L=._a1ki o4m2^:}fedw,ycIrCvpTs3n%Pg)ulF!;Sétx9àRbAh867050D0C0$0p0s0W0O0t0H0W0p0O0O0m010$0s0M010406050O0V0w0w0p0J0G040!0u0W0V140u0Q0t020p0w0M0Z0t0*0C1e0J0e0V0C0O050f1b1d1f1h190M04051M1F1P0f1M190D0s0L0|0~10120-0s0T0-0W1%0-0$17050@0+0W0C1Y0 11011$1(1*1(0$1:1=1.0$0J1N0$0-0|1k0O0M0p0Q120x011@1!010B0_0C0Q1s0C1.2a2c2h1_2k1=2n0w2p040c0t0S0J0u0M0u0O0s1n1p0=280J0J0C0H2K1F2r0Q1N0f262W2325241/0D2t121*0Q2m2H1.1V1X0}1^2*0s2,0Q0u2:1.0M2P1N2U2W311a2b1p2=2i2`0J1e0W170t0q2T3518342s371_393b3d0x3g2c3i2U2)013n0p3c040t0P3r2V193u3l123x3z0t0v3D3t353v3J3d0d3N3F3P3H3w0u3a3y3d0/3U3j361Z3m3Z3o3A0:3(3G3+3I3-3#3A0.3;3W3?3Y3!3K0(3|3k3~3R040q0j3N1Q2 1F2:2Z0D252(3X0H2{2z0;1W1N2~0C303h4a4k0=4s442?010r0Q170B2E0w4a3=4z0E3d4H3}4z0Q4C041e264M4y2i4K3A4U3*4z4B170s1t3Z0$3N0t3)3Q170O0e0J4+1G3h064`4.3X0r170=0B4Z3v4X4-4^3s4|450B171D0$0o4q0w0s0C0J523X16040g5k45170Q5p4z5m0U0z3U0t5z4-4I2i4~040s51562V5B4N385r4,584z0u17020W0$0Z5O5C1_5g173q5I4x4!2i5m5x5%065A5/5K4V1_5E2P0$0V0J5s5%5;5)5?0H170X3y0O0C5y5A5P5D4D3Z5X5L3m4 6d5=120u4X2^6h5 3I0+170J2c0T665%691_5m5o6w5Y125!045$336C015m0F6n3Q6q5F0Q4@6H6e126z5t5M044;4?6W6y176A6S6i3w5N6B6T6J170U0U6M3X5R040i6?3~6E3f6-6*5v5,315.5:5z6x125E5G6{4O6,315~3v6^0R7b6X0D7j1_6^0m0m7m6D0s17496 6o6/04724_7575774A6r0?5`5|7e7E0r6104630`6v735/7L7G5_5{7r4A7N0N0J1C3(0f4v4r4b7+0f4e1F0$4g7:2$2X0p1;7-4e1L5(3v2P0w0o0B0p0r0C0o0-0P171x1z1B1D0t7A571S3i1M0l1?0$5c0t2~2F2H0#0t0s0H0s0t8o0C0%230h2y2y6Q0t7$1V8F0@0s2P0n0t0I0W0t2,8p0C1m8p0 0t0h231?5g0{2m0t0a0V0L2P0t0D2c0{1=0|8Y2M0T6s0Q0D0{2`0w0+2P8(6Q5h0J0O0n1Q8j040,0t148#8/008A1y0M1=0F8y1p0B0#8-950t0x0j0x0v9m8?9k0V0{8`2c2(8 911?5f9s4k4P0V8y0O0$7f3X1f2J0-4S8A17090g0x0y0k0.0x090F0d0.0(9*0(0P0P0A0t0b3e096=5%8O060K1?9G8.0O000#0H0J2J0t0p0L2Q9R3~9T269W0%9Y9!0v9*0.0/9)0F0j0v0.9`4,0H1$0B4E8e8)0+0 1?7Eaf9V0p8nai049Z48au9|997}0,0M9k0s1B0#1?0)0|a00u902P9y0p0t0w0#264l8p2E2G0OaX8u8w8Sa51D2I8n6sa82m0L8M1oad4zaGahaj096Z0$0k9#9%ap9,9.0F9:9=9@3e0AaO7e0L0#a72k0HaI0s1o970n8O9 8Sa$9H0ta3a5a79Qaaac9A0{2MaFbJaHaJaj0q9)9{7e5g0W1*by8/1?aw5Gaz0{0YaQ4d0?0^0`04.

Évaluations restantes : 10/10

.339.8722.1280135q/(ê+0{L=._a1ki o4m2^:}fedw,ycIrCvpTs3n%Pg)ulF!;Sétx9àRbAh867050D0C0$0p0s0W0O0t0H0W0p0O0O0m010$0s0M010406050O0V0w0w0p0J0G040!0u0W0V140u0Q0t020p0w0M0Z0t0*0C1e0J0e0V0C0O050f1b1d1f1h190M04051M1F1P0f1M190D0s0L0|0~10120-0s0T0-0W1%0-0$17050@0+0W0C1Y0 11011$1(1*1(0$1:1=1.0$0J1N0$0-0|1k0O0M0p0Q120x011@1!010B0_0C0Q1s0C1.2a2c2h1_2k1=2n0w2p040c0t0S0J0u0M0u0O0s1n1p0=280J0J0C0H2K1F2r0Q1N0f262W2325241/0D2t121*0Q2m2H1.1V1X0}1^2*0s2,0Q0u2:1.0M2P1N2U2W311a2b1p2=2i2`0J1e0W170t0q2T3518342s371_393b3d0x3g2c3i2U2)013n0p3c040t0P3r2V193u3l123x3z0t0v3D3t353v3J3d0d3N3F3P3H3w0u3a3y3d0/3U3j361Z3m3Z3o3A0:3(3G3+3I3-3#3A0.3;3W3?3Y3!3K0(3|3k3~3R040q0j3N1Q2 1F2:2Z0D252(3X0H2{2z0;1W1N2~0C303h4a4k0=4s442?010r0Q170B2E0w4a3=4z0E3d4H3}4z0Q4C041e264M4y2i4K3A4U3*4z4B170s1t3Z0$3N0t3)3Q170O0e0J4+1G3h064`4.3X0r170=0B4Z3v4X4-4^3s4|450B171D0$0o4q0w0s0C0J523X16040g5k45170Q5p4z5m0U0z3U0t5z4-4I2i4~040s51562V5B4N385r4,584z0u17020W0$0Z5O5C1_5g173q5I4x4!2i5m5x5%065A5/5K4V1_5E2P0$0V0J5s5%5;5)5?0H170X3y0O0C5y5A5P5D4D3Z5X5L3m4 6d5=120u4X2^6h5 3I0+170J2c0T665%691_5m5o6w5Y125!045$336C015m0F6n3Q6q5F0Q4@6H6e126z5t5M044;4?6W6y176A6S6i3w5N6B6T6J170U0U6M3X5R040i6?3~6E3f6-6*5v5,315.5:5z6x125E5G6{4O6,315~3v6^0R7b6X0D7j1_6^0m0m7m6D0s17496 6o6/04724_7575774A6r0?5`5|7e7E0r6104630`6v735/7L7G5_5{7r4A7N0N0J1C3(0f4v4r4b7+0f4e1F0$4g7:2$2X0p1;7-4e1L5(3v2P0w0o0B0p0r0C0o0-0P171x1z1B1D0t7A571S3i1M0l1?0$5c0t2~2F2H0#0t0s0H0s0t8o0C0%230h2y2y6Q0t7$1V8F0@0s2P0n0t0I0W0t2,8p0C1m8p0 0t0h231?5g0{2m0t0a0V0L2P0t0D2c0{1=0|8Y2M0T6s0Q0D0{2`0w0+2P8(6Q5h0J0O0n1Q8j040,0t148#8/008A1y0M1=0F8y1p0B0#8-950t0x0j0x0v9m8?9k0V0{8`2c2(8 911?5f9s4k4P0V8y0O0$7f3X1f2J0-4S8A17090g0x0y0k0.0x090F0d0.0(9*0(0P0P0A0t0b3e096=5%8O060K1?9G8.0O000#0H0J2J0t0p0L2Q9R3~9T269W0%9Y9!0v9*0.0/9)0F0j0v0.9`4,0H1$0B4E8e8)0+0 1?7Eaf9V0p8nai049Z48au9|997}0,0M9k0s1B0#1?0)0|a00u902P9y0p0t0w0#264l8p2E2G0OaX8u8w8Sa51D2I8n6sa82m0L8M1oad4zaGahaj096Z0$0k9#9%ap9,9.0F9:9=9@3e0AaO7e0L0#a72k0HaI0s1o970n8O9 8Sa$9H0ta3a5a79Qaaac9A0{2MaFbJaHaJaj0q9)9{7e5g0W1*by8/1?aw5Gaz0{0YaQ4d0?0^0`04.

Version avec une boucle while

Le calcul d'une racine carrée est coûteux. Il est possible de s'en passer en observant que si $d$ est un entier positif tel que $d \le \sqrt{n}$ alors on a nécessairement $d^2 \le n$.

Cette observation permet de parcourir tous les diviseurs souhaités à l'aide d'une boucle while.

Version videVersion à trous

Évaluations restantes : 10/10

.339.8722.1280135q/(ê+0{L=._a1ki o4m2^:}fedw,ycIrCvpTs3*n%Pg)ulF!;Sétx9àRbAh867050D0C0%0p0s0X0O0t0H0X0p0O0O0m010%0s0M010406050O0W0w0w0p0J0G040#0u0X0W150u0R0t020p0w0M0!0t0+0C1f0J0e0W0C0O050f1c1e1g1i1a0M04051N1G1Q0f1N1a0D0s0L0}0 11130.0s0U0.0X1(0.0%18050^0,0X0C1Z1012011%1)1+1)0%1;1?1/0%0J1O0%0.0}1l0O0M0p0R130x011^1#010B0`0C0R1t0C1/2b2d2i1`2l1?2o0w2q040c0t0T0J0u0M0u0O0s1o1q0?290J0J0C0H2L1G2s0R1O0f272X2426251:0D2u131+0R2n2I1/1W1Y0~1_2+0s2-0R0u2;1/0M2Q1O2V2X321b2c1q2?2j2{0J1f0X180q2U3619352t381`3a3c180x3g2d3i2V2*013n0p3d040P3r2W1a3u3l133x3z0v3C3t363v3I180d3L3E3N3G3w0u3b3y180:3S3j371!3m3X3o040;3$3F3)3H3+3Z040/3/3U3;3W3Y3z0)3L1R301G2;2!0D262)3V0H2|2A0=1X1O2 0C313h414b0?4j3k3|0r180?0B413:2@010E180t4v3{4x0R0B181E0%0o4h0w0s0C0J4C4p4x17040g4Q3(4E180R4W3v4T0V0z3S0t4+4B4w2j4r040s4u1H3h4-4D394Z3L4_4R2j0u18020X0%0!4}3%3v4M3p4#3V4T4)4@3s064,5j4~4X4/182Q0%0W0J4!5g2W5l3v0r0H180Y3y0O0C4*4,583V0R4s574.1`51040m5L4`1`5a043q5u195j5H4q180E1%1?5R4 3m5K5X5w3V5O0Q0Q5*5m5T0s5b5.5!4x5O53555Q5|5M3H4|5X5}2j5e5F5k5/5#4;4?326d4Y045t6h685N180S5@3O5-6m64015O0m626u5S135U0j5c3|6a5X5i6c5k6n134:5p5r6l4^6M015y5A5C5E6I6K6i4{040D6r5:180i6z6S6v5U3f6Z5G6v6O0@6Q6)4q5z040N0J1D3$0f4m4i42750f451G0%477a2%2Y0p1=77451M4o5^132Q0w0o0B0p0r0C0o0.0P181y1A1C1E0t5f341T3i1N0l1@0%4I0t2 2G2I0$0t0s0H0s0t7M0C0(240h2z2z0R0%0t701W7%0^0s2Q0n0t0I0X0t2-7N0C1n7N100t0h241@4M0|2n0t0a0W0L2Q0t0D2d0|1?0}7~2N0U0J2d0D0|2{0w0,2Q847(4N0J0O0n1R7H040-0t15818b007Y1z0M1?0F7W1q0B0$898u0t0x0j0x0v8L8f8J0W0|8j8l7^0u8p8a4L8R4b0R0R0W7W0O7)6T1g2K0.1f7L0(18090g0x0y0k0/0x090F0d0/0)970)0P0P0A0t0b0t0q090V3L7;060K1@8o8q1@0O000$0H0J2K0t0p0L2R6#1`8_278|7Y8 910v970/0:960F0j0v0/9l4}0H1%0B0B8r8M0t0,101@8^9z9I0p8}9L0q0j9W5X8x7G7k0-0M8J0s1C0$1@0*0}9r8)9t8X0p0t0w0$274c7N2F2H0Oa17S7U7^9x1E2J7L8k9A2n0L7/1p9F139H8{9/9K0490090O0e0J0%0k92949R999b0F9d9f9h9j0A9@6h0L0$9z2l0H9/0s1p8w0n7;9q8(8*9u9w9y9A9C9E8Z0|2N9,8`9J8~aD0g0q969m5.4M0X1+a)8b1@9Y4=9#7C0Z8y1a780@0_0{04.

Évaluations restantes : 10/10

.339.8722.1280135q/(ê+0{L=._a1ki o4m2^:}fedw,ycIrCvpTs3*n%Pg)ulF!;Sétx9àRbAh867050D0C0%0p0s0X0O0t0H0X0p0O0O0m010%0s0M010406050O0W0w0w0p0J0G040#0u0X0W150u0R0t020p0w0M0!0t0+0C1f0J0e0W0C0O050f1c1e1g1i1a0M04051N1G1Q0f1N1a0D0s0L0}0 11130.0s0U0.0X1(0.0%18050^0,0X0C1Z1012011%1)1+1)0%1;1?1/0%0J1O0%0.0}1l0O0M0p0R130x011^1#010B0`0C0R1t0C1/2b2d2i1`2l1?2o0w2q040c0t0T0J0u0M0u0O0s1o1q0?290J0J0C0H2L1G2s0R1O0f272X2426251:0D2u131+0R2n2I1/1W1Y0~1_2+0s2-0R0u2;1/0M2Q1O2V2X321b2c1q2?2j2{0J1f0X180q2U3619352t381`3a3c180x3g2d3i2V2*013n0p3d040P3r2W1a3u3l133x3z0v3C3t363v3I180d3L3E3N3G3w0u3b3y180:3S3j371!3m3X3o040;3$3F3)3H3+3Z040/3/3U3;3W3Y3z0)3L1R301G2;2!0D262)3V0H2|2A0=1X1O2 0C313h414b0?4j3k3|0r180?0B413:2@010E180t4v3{4x0R0B181E0%0o4h0w0s0C0J4C4p4x17040g4Q3(4E180R4W3v4T0V0z3S0t4+4B4w2j4r040s4u1H3h4-4D394Z3L4_4R2j0u18020X0%0!4}3%3v4M3p4#3V4T4)4@3s064,5j4~4X4/182Q0%0W0J4!5g2W5l3v0r0H180Y3y0O0C4*4,583V0R4s574.1`51040m5L4`1`5a043q5u195j5H4q180E1%1?5R4 3m5K5X5w3V5O0Q0Q5*5m5T0s5b5.5!4x5O53555Q5|5M3H4|5X5}2j5e5F5k5/5#4;4?326d4Y045t6h685N180S5@3O5-6m64015O0m626u5S135U0j5c3|6a5X5i6c5k6n134:5p5r6l4^6M015y5A5C5E6I6K6i4{040D6r5:180i6z6S6v5U3f6Z5G6v6O0@6Q6)4q5z040N0J1D3$0f4m4i42750f451G0%477a2%2Y0p1=77451M4o5^132Q0w0o0B0p0r0C0o0.0P181y1A1C1E0t5f341T3i1N0l1@0%4I0t2 2G2I0$0t0s0H0s0t7M0C0(240h2z2z0R0%0t701W7%0^0s2Q0n0t0I0X0t2-7N0C1n7N100t0h241@4M0|2n0t0a0W0L2Q0t0D2d0|1?0}7~2N0U0J2d0D0|2{0w0,2Q847(4N0J0O0n1R7H040-0t15818b007Y1z0M1?0F7W1q0B0$898u0t0x0j0x0v8L8f8J0W0|8j8l7^0u8p8a4L8R4b0R0R0W7W0O7)6T1g2K0.1f7L0(18090g0x0y0k0/0x090F0d0/0)970)0P0P0A0t0b0t0q090V3L7;060K1@8o8q1@0O000$0H0J2K0t0p0L2R6#1`8_278|7Y8 910v970/0:960F0j0v0/9l4}0H1%0B0B8r8M0t0,101@8^9z9I0p8}9L0q0j9W5X8x7G7k0-0M8J0s1C0$1@0*0}9r8)9t8X0p0t0w0$274c7N2F2H0Oa17S7U7^9x1E2J7L8k9A2n0L7/1p9F139H8{9/9K0490090O0e0J0%0k92949R999b0F9d9f9h9j0A9@6h0L0$9z2l0H9/0s1p8w0n7;9q8(8*9u9w9y9A9C9E8Z0|2N9,8`9J8~aD0g0q969m5.4M0X1+a)8b1@9Y4=9#7C0Z8y1a780@0_0{04.