Tester la primalité d'un entier : méthode (MPSI)

Pour savoir si $n \geqslant 2$ est premier :

1. Lister les nombres premiers $p \leqslant \sqrt{n}$.
2. Tester si l'un d'eux divise $n$.
3. Si aucun ne divise $n$, alors $n$ est premier ; sinon $n$ est composé.

Exemple : $\sqrt{223} \approx 14{,}9$. On teste $2, 3, 5, 7, 11, 13$ : $223$ est impair, la somme de ses chiffres $7$ n'est pas multiple de $3$, il ne finit ni par $0$ ni par $5$, et $7 \times 31 = 217$, $11 \times 20 = 220$, $13 \times 17 = 221$ montrent que $7, 11, 13$ ne le divisent pas. Donc $223$ est premier. En revanche $221 = 13 \times 17$ est composé.

Le crible d'Ératosthène liste les premiers jusqu'à $N$ : on barre les multiples stricts de $2$, puis de $3$, puis du plus petit nombre non barré, et ainsi de suite jusqu'à $\sqrt{N}$.