Me hizo gracia el código de eferion , seguro que yo cobraria más barato que el y admito muchas formas de pago (paypal, bitcoins...)... Ya en serio, fuera bromas, puedes utilizar el método de la cripta de erastóstenes (hay métodos muchos más rápidos) pero si no te especifican nada, prueba a implementarlo: