Ti conviene cercare "algoritmo AKS" perchè, anche se è complicato, garantisce alte prestazioni soprattutto con un input elevato.
Ho dato uno sguardo veloce all'algoritmo AKS e da quanto ho capito (la lettura è stata mooolto veloce quindi c'è una possibilità che possa sbagliarmi) usa lo stesso criterio probabilistico dell'algoritmo indicato nel link che l'autore del 3d ha postato,perciò non da la certezza della primalità,d'altra parte però per numeri molto grandi non bisogna aspettare il tempo di vita dell'universo con quello