swf: Есть, наверно, готовые разложения натуральных чисел на простые множители. Сразу пользоваться этими разложениями.
А вот сравнение разложения проверяемого числа на простые множители с разложением НОК'а на предмет недостающих сомножителей зависит от того, как эти разложения хранятся.
За счёт увеличения памяти можно ускорить процедуру сравнения.

https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833983