Идея по разложению чисел на множители Пусть нужно разложить число N (на всякий случай будем считать, что N нечётное). Рассмотрим функцию f(x)=НОД(x!,N). Пусть M - наименьший нетривиальный делитель N. Тогда f(x)=1 при x=M. (x! нужно вычислять по модулю N, поэтому возможна ситуация f(x)=0) M можно найти за O(log(N)) вычислений факториала. Если M=N, то N - простое. Иначе найден простой делитель, дальше аналогично. Знает ли кто-нибудь быстрый алгоритм вычисления факториалов? IMHO задача не выглядит безнадёжно трудоёмкой. Мне кажется, что можно попробовать так: Сначала нужно придумать, как вычислять произведение 2^n последовательных чисел. Факториал можно составить из O(log(N)) таких произведений. Это произведение можно записать в виде x(x+1)(x+2)...(x+1+2+...+2^(n-1)). Выглядит не очень симметрично, но это можно исправить. Достаточно записать как произведение сомножителей вида (y+-a1+-a2+-a3...). Здесь получаются полуцелые слагаемые, но это не проблема. Нужно домножить на 2^(2^n), при этом НОД(...,N) сохраняется. В результате имеем произведение сомножителей вида (z+-1+-2...+-2^(n-1)). Что с этим дальше делать, я пока не придумал, но тут бросается в глаза чудовищное дублирование вычислений и напрашивается что-то в стиле FFT или динамического программирования.