Qui non si risolvono esercizi, vedi il regolamento. Devi proporre tu una soluzione.

La più banale per il check è controllare che i numeri fino a sqrt(n) non dividano n.
Poi c'è il crivello di Eratostene.
Poi i vari test probabilistici.