На нашем сайте мы используем cookie для сбора информации технического характера и обрабатываем IP-адрес вашего местоположения. Продолжая использовать этот сайт, вы даете согласие на использование файлов cookies. Здесь вы можете узнать, как мы пользуемся файлами cookies.
Я согласен
логотип upread.ru

Эффективная программа для получения всех простых множителей заданного числа на 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, либо простым числом.




Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

тегизаметки, php, задачи





Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.



Обзор Java Date и Time API
Воспроизведение mp3 на C#: пример и плеер


© upread.ru 2013-2023
При перепечатке активная ссылка на сайт обязательна.
Задать вопрос
письмо
Здравствуйте! Вы можете задать мне любой вопрос. Если не получается отправить сообщение через эту форму, то пишите на почу up777up@yandex.ru
Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.