confusedНо ошибся поисковиком и попал на статью индийских ученых, опубликованную в 2002 году.
Там дается весьма эффективный алгоритм определения "простоты" числа, для математиков будет интересно.
С наброском алгоритма решения типовой задачи. Так вот обратите внимание на строчку 6 алгоритма. Про прохождении каждой итерации требуется нахождение максимального простого сомножителя, эээээ... Получается эдакое осовремененное решето Эратосфена, разве нет?
Статья: PRIMES is in P (Manindra Agrawal, Neeraj Kayal and Nitin Saxena)
