|
Эффективная программа для получения всех простых множителей заданного числа на PHPЕсть задача. Дано некое число n, напишите эффективную функцию для вывода всех простых множителей n. Например, если входное число равно 12, то на выходе должно быть "2 2 3". Если входное число равно 315, то на выходе должно быть "3 3 5 7". Давайте решим её на PHP. Первый подход Ниже приведены шаги по поиску всех простых множителей.
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 приведенного выше алгоритма мы запускаем цикл и делаем в цикле следующее:
 Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.  заметки, php, задачи |
|
Программы на заказ
Отзывы
Контакты| © upread.ru 2013-2023 При перепечатке активная ссылка на сайт обязательна. |
