Es muy sencillo. En un bucle metes el número a comprobar que se divida con exactitud entre el 2 y un número entero menos que él mismo, y si en algún momento se encuentra alguno, ese número no es primo. Es más, incluso te diré que ese mismo bucle lo puedes poner que se repita hasta la mitad del número introducido, ya que si no es divisible entre la primera mitad, tampoco lo será entre la segunda.