Il primo che mi viene in mente è dividere il numero specificato per tutti i numeri minori della sua metà, appena trovi una divisione che non dà resto sai che il numero non è primo, altrimenti lo è...

Edit: anzi per ottimizzarepotresti far dividere per tutti i numeri dispari minori della sua metà (aggiungendo a questi il 2)