Рубрики

Java-программа для эффективной печати всех простых факторов заданного числа

Для числа n напишите эффективную функцию для вывода всех простых множителей n. Например, если введено число 12, тогда вывод должен быть «2 2 3». А если номер входа 315, то выход должен быть «3 3 5 7».
Ниже приведены шаги, чтобы найти все основные факторы.
1) Пока n делится на 2, выведите 2 и разделите n на 2.
2) После шага 1 n должно быть нечетным. Теперь начните цикл с i = 3 до квадратного корня из n. Пока i делит n, выведите i и разделите n на i, увеличьте i на 2 и продолжите.
3) Если n простое число и больше 2, то n не превратится в 1 за два вышеуказанных шага. Поэтому выведите n, если оно больше 2.

// Программа для печати всех основных факторов

import java.io.*;

import java.lang.Math;

  

class GFG {

    // Функция для печати всех простых факторов

    // данного числа n

    public static void primeFactors(int n)

    {

        // Вывести число 2, которые делят n

        while (n % 2 == 0) {

            System.out.print(2 + " ");

            n /= 2;

        }

  

        // n должно быть нечетным в этой точке. Значит мы можем

        // пропустить один элемент (Примечание i = i +2)

        for (int i = 3; i <= Math.sqrt(n); i += 2) {

            // Пока я делю n, выводим i и делим n

            while (n % i == 0) {

                System.out.print(i + " ");

                n /= i;

            }

        }

  

        // Это условие должно обрабатывать случай, когда

        // n простое число больше 2

        if (n > 2)

            System.out.print(n);

    }

  

    public static void main(String[] args)

    {

        int n = 315;

        primeFactors(n);

    }

}

Выход:

3 3 5 7

Как это работает?
Шаги 1 и 2 относятся к составным числам, а шаг 3 — к простым числам. Чтобы доказать, что полный алгоритм работает, нам нужно доказать, что шаги 1 и 2 действительно заботятся о составных числах. Это ясно, что шаг 1 заботится о четных числах. И после шага 1 все оставшиеся простые множители должны быть нечетными (разница двух простых множителей должна быть не менее 2), это объясняет, почему i увеличивается на 2.
Теперь основная часть заключается в том, что цикл продолжается до корня квадратного из n, а не до. Чтобы доказать, что эта оптимизация работает, рассмотрим следующее свойство составных чисел.
Каждое составное число имеет по крайней мере один простой множитель, меньший или равный квадратному корню из себя.
Это свойство может быть доказано с помощью встречного утверждения. Пусть a и b два таких фактора n, что a * b = n. Если оба больше √n, то ab> √n, * √n, что противоречит выражению «a * b = n».

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

Пожалуйста, обратитесь к полной статье об эффективной программе, чтобы распечатать все основные факторы заданного числа для более подробной информации!

Рекомендуемые посты:

Java-программа для эффективной печати всех простых факторов заданного числа

0.00 (0%) 0 votes