Эффективная программа для получения всех простых множителей заданного числа на PHP

Есть задача. Дано некое число n, напишите эффективную функцию для вывода всех простых множителей n. Например, если входное число равно 12, то на выходе должно быть "2 2 3". Если входное число равно 315, то на выходе должно быть "3 3 5 7". Давайте решим её на PHP.

Первый подход

Ниже приведены шаги по поиску всех простых множителей.

1. Пока n делится на 2, выведите 2 и разделите n на 2.
2. После шага 1 n должно быть нечетным. Теперь запустите цикл от i = 3 до квадратного корня из n. Пока i делит n, выведите i и разделите n на i. После того, как i не сможет разделить n, увеличьте i на 2 и продолжайте.
3. Если n является простым числом и больше 2, то n не станет 1 с помощью двух вышеуказанных шагов. Поэтому выведите n, если оно больше 2.

Код функции

function printPrimeFactors($n) 
{ 
    while($n % 2 == 0) 
    { 
        echo 2," "; 
        $n = $n / 2; 
    } 
  
    // n, должно быть нечетным в этой точке
    // Так что мы можем пропустить один элемент (Note i = i +2) 
    for ($i = 3; $i <= sqrt($n);  $i = $i + 2) { 
          
        // Пока i делится n,  
        // печатаеми i и делим n 
        while ($n % $i == 0) { 
            echo $i," "; 
            $n = $n / $i; 
        } 
    } 
  
    //Это условие заключается в том, чтобы
	// обрабатывать случай, когда n
	// является простым числом, большим 2
    if ($n > 2) {
    	 echo $n," "; 
    }       
} 

Пример работы (вызов)

$n = 999; 
printPrimeFactors($n); 

Временная сложность (Общее время алгоритма): O(sqrt(n))

В худшем случае (когда либо n, либо sqrt(n) является простым числом, например: возьмите n=11 или n=121 для обоих случаев, цикл for выполняется sqrt(n) раз), цикл for выполняется для sqrt(n) раз. Чем больше раз цикл while выполняет итерацию числа, тем меньше исходное n, что также уменьшает значение sqrt(n). Хотя временная сложность в лучшем случае равна O(log(n)), когда простые множители n равны только 2 и 3 или n имеет вид (2^x*(3^y), где x>=0 и y> =0.

Вспомогательное пространство (Пространственная сложность): O(1)

Как это работает?

Шаги 1 и 2 касаются составных чисел, а шаг 3 — простых чисел. Чтобы доказать, что весь алгоритм работает, нам нужно доказать, что шаги 1 и 2 действительно обрабатывают составные числа. Понятно, что шаг 1 касается четных чисел. И после шага 1 все оставшиеся простые множители должны быть нечетными (разница двух простых множителей должна быть не менее 2), это объясняет, почему i увеличивается на 2.

Теперь основная часть заключается в том, что цикл выполняется до тех пор, пока не будет получен квадратный корень из n, а не до тех пор, пока n. Чтобы доказать, что эта оптимизация работает, давайте рассмотрим следующее свойство составных чисел.

Каждое составное число имеет по крайней мере один простой делитель, который меньше или равен квадратному корню из самого себя.

Это свойство можно доказать с помощью встречного утверждения. Пусть a и b — два фактора числа n такие, что a*b = n. Если оба больше √n, то a.b > √n, * √n, что противоречит выражению «a * b = n».

На шаге 2 приведенного выше алгоритма мы запускаем цикл и делаем в цикле следующее:

• а) Найдите наименьший простой множитель i (должен быть меньше √n,)
• б) Удалить все вхождения i из n, многократно разделив n на i.
• в) Повторите шаги a и b для разделенного n и i = i + 2. Шаги а и б повторяются до тех пор, пока n не станет либо 1, либо простым числом.