Info U:
Cribles:
0. Un entier naturel est sans carré ssi il n'admet aucun diviseur carré parfait autre que $1$. Donner un algorithme de complexité linéaire qui renvoie le nombre d'entiers sans carré inférieurs ou égaux à $n$.
On note $\pi(n)$ le nombre de nombres premiers dans $[\![ 1,n ] \!]$. On admet le théorème des nombres premiers: $\pi(n) \sim \frac{n}{\operatorname{ln}(n)}$ ainsi que $p_n \sim n \operatorname{ln} (n)$ où $p_n$ est le $n$-ième nombre premier.
1. Donner un algorithme calculant $\pi(n)$, donner sa complexité.
2. Donner une structure de données qui code une partie $E$ de $[\![ 1,n ] \!]$ telle que:
$i$) l'initialisation se fasse en $O(n)$,
$ii$) la suppression d'un élément en $O(1)$,
$iii$) le parcours des éléments de $E$ en $O(|E|)$.
3. En déduire un algorithme de complexité linéaire répondant à la question 1.
4. Donner un algorithme calculant le pgcd de deux entiers et donner sa complexité.
Indication(s) fournie(s) par l'examinateur pendant l'épreuve0. Regarder le titre du sujet (Cribles).
Commentaires divers
À chaque question, l'examinateur demandait la complexité en temps et en espace des algorithmes.
Le sujet exact et en entier sera probablement dans le prochain rapport de jury.
Aucun commentaire posté pour le moment