Comment tester la primalité d'un nombre ?

En vérifiant qu'aucun entier premier $p \leq \lfloor\sqrt{n}\rfloor$ ne divise $n$ (test de divisibilité exhaustif)

Tester la primalité de $n$ en essayant de le diviser par tous les premiers jusqu'à $\lfloor\sqrt{n}\rfloor$.

En appliquant le test de Fermat : si $a^{n-1} \not\equiv 1 \pmod{n}$ pour un entier $a$ avec $\mathrm{pgcd}(a,n)=1$, alors $n$ est composé

Utiliser le test probabiliste de Fermat pour détecter rapidement qu'un nombre est composé, en exploitant la contraposée du petit théorème de Fermat.