Прост ==Полиномиален.Алгоритм то прост, но, думаю, v04bvs имел ввиду, что чем больше простое число , тем утомительнее(не сложнее )) проверять его
Это означает еще один мильён за проверку на простоту числа с > 300 знаков
Одно число проверить можно.
Тяжело их искать, т.к если добираться до 300-го знака по шагам, то это неизмеримо с нашей жизнью.