|
Самый простой способ это перебирать, числа от 1 до корня из N, и смотреть делится или нет.
Есть тест Рабина-Карпа, но там ответ дается с вероятностью. Чем больше испытаний тем ближе она к единице.
Если интересно можно почитать Акритаса или Винограда или Бухштаба. Обычно книги называется теория чисел (number theory).
|