[PDF] Crible dEratosth`ene [th05] - Examen

View - Download Crible dEratosth`ene [th05] - Examen

Previous PDF

Next PDF

Crible d'Eratosthene [th05] - Examen

Karine Zampieri, Stephane Riviere

UniscielalgoprogVersion 22 mai 2018

Table des matieres

1 Crible d'Eratosthene / pgeratos

2

1.1 Algorithme du Crible(5 points). . . . . . . . . . . . . . . . . . . . . .2

1.2 Liste des nombres premiers(4 points). . . . . . . . . . . . . . . . . . .7

1.3 Programme(1 point). . . . . . . . . . . . . . . . . . . . . . . . . . . .8

1.4 Analyse mathematique

9

1.5 Spirale du crible

10

2 References generales

1 0 Python - Crible d'Eratosthene (Solution)Mots-ClesTheorie des nombres

RequisAxiomatique imperative sauf Fichiers

Diculte• • ◦Objectif

Cet exercice determine tous les nombres premiers inferieurs a un entiernpar la methode du crible d'Eratosthene. ...(enonce page suivante)... 1

Unisciel algoprog { Crible d'Eratosthene [th05]2

1 Crible d'Eratosthene / pgeratos

1.1 Algorithme du Crible (5 points)Denition

Unentierest ditpremiers'il possede exactement deux diviseurs : 1 et lui-m^eme appeles diviseurs triviaux. Sinon il est ditcomposite.Propriete Lecrible d'Eratosthene1permet de conna^tre en une seule fois un grand nombre d'entiers naturels premiers consecutifs et pas trop grands (par exemple inferieurs a un milliard).Algorithme du crible Pour conna^tre tous les nombres premiers jusqu'anfaire : •Marquez aVraitous les entiers de 2 jusqu'an. •Marquez aFauxtous les multiples de 2 sauf 2. •A partir de 3, repetez les deux points suivants et arr^etez-vous des quen/2est atteint (ou mieux : la racine carree den) : 1.

R eperezl ep remieren tierimpairkencore present.

2.

Ma rquez aFauxtous ses multiples saufk.

Ce qui reste est la liste des nombres premiers jusqu'an.Exemple Considerons l'applet deWikipedia:Pour obtenir les nombres premiers inferieurs a 120 :

1. Mathematicien et philosophe, connu pour ses travaux en arithmetique et en geometrie,Eratos-

th enevecut au IIIesiecle avant J.C. a Alexandrie.

Unisciel algoprog { Crible d'Eratosthene [th05]3

•Barrez tous les multiples de 2 (donc 4, 6, 8, etc., 118, 120) •Puis tous les multiples de 3 (donc 6, 9, 12, etc., 117, 120) •Puis tous les multiples de 5 (donc 10, 15, 20, etc., 115, 120) •Puis tous les multiples de 7 (donc 14, 21, 28, etc., 112, 119) •Et s'arr^eter a 11 car112= 121>120.

7). Ces qui reste (les non barres) est la liste des entiers premiers inferieurs a 120.Analyse

On utilise un tableau unidimensionnel de booleens de taillen+ 1, ou on fait en sorte que l'element a l'indiceisoit egal aVraisiiest premier. Ni l'entier0, ni l'entier1(tous les nombres en sont ses multiples) ne sont premiers. Les calculs seront donc executes a partir de2. Au depart, tous les elements du tableau sont initialises aVraisauf pour les deux premiers elements initialises aFaux. Dans le traitement iteratif, les nombres non premiers seront etape necessite une nouvelle variable correspondant a ces multiples). Cette suppression commence a partir dei2car les multiples deistrictement inferieurs ai2ont ete supprimes dans les iterations precedentes. Eectivement, tous les multiples deisont :2×i,3×i,...,(i-1)×i,i2,(i+ 1)×i,...(sans depassernet sans inclure, au debut, le nombre couramment analyse,i, car il est premier). Mais la valeur2×iest aussi un multiple de 2, deja elimine a l'etape de suppression des multiples de 2, la valeur

3×iest aussi un multiple de 3 deja elimine a l'etape de suppression des multiples de 3,

etc. Le plus petit multiple qui n'a pas ete supprime dans les etapes precedentes, selon ce raisonnement, esti2. En appliquant ce mecanisme, nous pouvons demontrer que l'operation de suppression puis le typeCriblecomme etant un tableau deCMAXbooleens.(1 point) Ecrivez une procedureinitialiserCrible(c,n)qui initialise aVrailes elements d'unCriblec [..n]. Par defaut tous les nombres sont premiers. Marquez aFaux, les en- tiers0et1.Solution Parametres

Entrants :L'entiern

Sortants :LeCriblec (1 point)

Ecrivez une procedureeliminerCrible(c,n,k)qui marque aFauxtous lesmul- tiples successifsdek(entier), a savoir2k,3k..., dans unCriblec [..n]. Unisciel algoprog { Crible d'Eratosthene [th05]4Solution Parametres

Entrants :Les entiersnetk

Modies :LeCriblec Solution simple

Les multiples deketant2k,3k..., donc on commence park+ket on incrementekdek a chaque tour de boucle.(1 point) Ecrivez une fonctionsuivantImpair(c,n,k)qui recherche et renvoie le suivant impairnon marque dek(entier impair) dans unCriblec [..n], et qui renvoie-1s'il n'existe pas (ce qui marquera la n de la recherche).Solution simple Le premier entier impairjqui suitkestk+2. Tant qu'il est inferieur ou egal anet que c[j]estFaux, on passe a l'entier impair suivant en incrementantjde2. A la sortie de la boucle, sijest plus grand quen, alors c'est ni, sinon c'estj.

Unisciel algoprog { Crible d'Eratosthene [th05]5

Ecrivez le code sur cette partie...

Unisciel algoprog { Crible d'Eratosthene [th05]6Validez vos denitions, procedures et fonction avec la solution.

Solution Python@[pgeratos.py]definitialiserCrible(n):c= [] forjinrange (0,n+1):c+= [ True] c [0] = c [1] = False returncdefeliminerCrible(c,n,k):forjinrange (k+k,n+1,k):c[j] =False defsuivantImpair(c,n,k):j= k + 2 while(j<= n andnot c[j]):j+= 2 returnjif(j<= n )else-1(1 point) Ecrivez une procedureeratosCrible(c,n)qui calcule les nombres premiers com- pris entre1etndans unCriblec . La procedure comporte trois parties : •L'initialisation par appel de la procedureinitialiserCrible. •L'elimination (procedureeliminerCrible) de tous les multiples de2(2est le plus petit nombre premier). •L'elimination de tous les multiples successifs de chaque entierimpairen commen- cant par le plus petit3.Solution Parametres

Entrants :L'entiern

Sortants :LeCriblec De m^eme, ecrivez une procedureeratosCrible2(c,n)qui calcule les nombres premiers

compris entre 1 etndans unCriblec comme suit : •L'initialisation par appel de la procedureinitialiserCrible.

Unisciel algoprog { Crible d'Eratosthene [th05]7

•L'elimination (procedureeliminerCrible) de tous les multiples de 2 (2 est le plus petit nombre premier). •L'elimination de tous les multiples successifs des entiersimpairsknon encore traites a partir de 3 tant que la racine carree denn'est pas atteinte.Aide simple Solution Python@[pgeratos.py]deferatosCrible(n):c= initialiserCrible (n) eliminerCrible c n , 2) ndiv2 n // 2 k = 3 while(k!= -1): eliminerCrible(c,n ,k ) k suivantImpair c ndiv2 k returncdeferatosCrible2(n):c= initialiserCrible (n) eliminerCrible c n , 2) k = 3 while(k*k<= n ):if(c[k]):eliminerCrible(c,n ,k ) returnc

1.2 Liste des nombres premiers (4 points)

Ce probleme determine la liste des nombres premiers inferieurs a un entier naturel donne.

(Pour 100000, il y a 9592 entiers premiers.) Il utilise la procedureeratosCrible.(1 point)Denissez la constanteTMAX=1000(nombre maximum de valeurs dans une liste),

eventuellement le typeITableaucomme etant un tableau d'entiers d'au plusTMAXentiers, puis le typeIListecomme etant une structure contenant : •UnITableaucontenant les valeurs. •Un entiertailledu nombre d'elements eectifs dans leITableau. Unisciel algoprog { Crible d'Eratosthene [th05]8(0.5 point) Ecrivez une procedureinitialiserListe(lt)qui initialise uneIListelt a la liste vide (aucun element, a savoir sa taille est nulle).(1 point) Ecrivez une procedureajouterElement(lt,valeur)qui ajoute une valeurvaleur (entier) dans uneIListelt (a la suite de ceux deja presents).Solution simple On ajoute la valeur dans le tableau des elements de laIListeet on incremente sa taille.(1 point) Ecrivez une procedurecreerListeNP(n,lt)qui cree la liste des entiers premiers inferieurs ou egaux andans uneIListelt .Solution simple On cree d'abord le crible par appel a la procedureeratosCrible: sic[k]est reste aVraialors kest premier. D'ou, on initialise d'abordlta la liste vide (procedureinitialiserListe) (ltest sortant) puis on traverse leCriblec et on ajoute alttous les elementskqui sont restes aVraidansc(c.-a.-d. sic[k]alorsajouterListe(lt,k)).(0.5 point) Ecrivez une procedureafficherListe(lt)qui ache les valeurs du tableau d'uneIListelt .

1.3 Programme (1 point)(1 point)

Ecrivez un script qui saisit un entier (suppose positif et inferieur aCMAX) puis

calcule et ache la liste des nombres premiers qui sont inferieurs ou egaux a cet entier.Testez. Exemple d'execution :

Entier

dans [1..99999]? 120

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

101 103 107 109 113

Validez votre script avec la solution.

Unisciel algoprog { Crible d'Eratosthene [th05]9

Ecrivez le code sur cette partie...Validez votre procedure avec la solution. Solution Python@[pgeratos.py]n= saisieEntier (1,CMAX-1) cb eratosCrible n forkinrange (0,n+1):if(cb[k]):print(k,"" ,sep="",end="")print()

1.4 Analyse mathematiqueProuvez qu'il est inutile d'etudier les entiersjmarques c.-a-d. sijn'est plus premier

alors tous ses multiples auront deja ete supprimes.Solution simple Sijest marque alorsjn'est pas premier car il peut s'ecrirej=k pavec1< ketp < j doncjest multiple dek(egalement dep). Tous les multiples dejsont aussi multiples

dek. Commekest inferieur aj, tous ses multiples sont deja marques.Prouvez que le premier multiple deja marquer estj2c.-a-d. les multiples2j,3j,...ont

deja ete supprimes.Solution simple Les multiples dejs'ecrivent2j,3j, ...,k j. Ork jest un multiple deket dejdonc si

k < jalorsk jest deja marque doncj2est le premier multiple dej.Deduisez une versioneratosOptm(c,n)optimisee.Solution simple

Les nombres non marques qui restent sont exactement les nombres premiers au plus egaux an: en eet, les nombres marques sont des multiples d'un de leurs predecesseurs, et ne sont donc pas premiers, et aucun des nombres non marques ne saurait ^etre non premier, car il serait alors un multiple d'un de ses predecesseurs, et aurait ete marque. De plus, il est inutile de poursuivre le marquage a partir du premier nombre non marque k >⎷n: en eet, un premier nombre non marque n'etant divisible par aucun de ses predecesseurs est necessairement premier, ses multiples par un de ses predecesseurs ont tous ete marques (en tant que multiple d'un diviseur premier d'un predecesseur), et par consequent, son premier multiple non marque estk2> n: il n'y a donc plus de marquage possible.

Unisciel algoprog { Crible d'Eratosthene [th05]10

1.5 Spirale du cribleDenition

On appelle lan-spirale des nombres premiers, dite aussiSpirale d'ULAM, la spirale des nombres1an(g. de gauche) ou on ache un point si le nombre est premier et rien sinon (g. de droite)

17 16 15 14 13

18 5 4 3 12

19 6 1 2 11

20 7 8 9 10

21 ...-→• •

Ecrivez une fonctiontracerSpirale(c,n)qui genere la spirale d'Ulamissu d'unCrible c n ].Aide simple Veriez que les droitesx+y, x+y-1etx-ydeterminent les quatre regions ou dans chacune il convient de faire : •++xquand (x-y≥0etx+y-1<0) •++yquand (x+y-1≥0etx-y >0) Comprend[Chappelier-CPP1 :c2 :ex9], [Chaty-PG1 :c7 :ex6], [Engel-AL1 :c2 :xm04], [Felea-PG1 :c3 :ex67], [Maunoury-AL1 :c7 :ex16]quotesdbs_dbs19.pdfusesText_25

[PDF] utilisation de l'argent métal

[PDF] alliage de l'argent

[PDF] les participes passés des verbes

[PDF] telecharger indicatif telephonique

[PDF] indicatifs téléphoniques internationaux portables

[PDF] propriétés de l'eau 5ème

[PDF] indicatif telephonique pays africains

[PDF] art et publicité aire sur la lys

[PDF] tableau des principales déductions 2017

[PDF] la publicité persuasive et informative

[PDF] pronoms numéraux exercices

[PDF] pronom numéraux

[PDF] tableau des pronoms personnels

[PDF] tableau des pronoms pdf

[PDF] tableau de tous les pronoms pdf