Простые числа и разложение на множители

См. видеозаписи лекций ЛКШ параллели C', раздел «Арифметические алгоритмы»