Ci sono molti altri algoritmi per verificare la primalità, anche basati su principi diversi da quelli illustrati finora.

Ci sono anche algoritmi più specializzati, che funzionano solo, o particolarmente bene, per classi speciali di numeri. Una di queste classi è costituita dai numeri di Mersenne, cioè quelli della forma

Si può mostrare che, se m è primo, allora  è primo o pseudoprimo, e che se m è pseudoprimo allora  è pseudoprimo. Questo mostra tra l'altro che ci sono infiniti pseudoprimi.

Il problema di fattorizzare interi è enormemente più complesso.