Рубрики

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

Для числа 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.

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

  

import math

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

def primeFactors(n):

      

    # Выведите число двух / s, которые делят n

    while n % 2 == 0:

        print 2,

        n = n / 2

          

    # n должен быть нечетным в этой точке

    # чтобы можно было пропустить 2 (i = i + 2)

    for i in range(3,int(math.sqrt(n))+1,2):

          

        # пока я делю n, печатать я делю n

        while n % i== 0:

            print i,

            n = n / i

              

    # Условие, если n простое число

    # число больше 2

    if n > 2:

        print n

          
Программа # Driver для проверки вышеуказанной функции

  

n = 315

primeFactors(n)

  
# Этот код предоставлен Harshit Agrawal

Выход:

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 или простому числу.

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

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

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

0.00 (0%) 0 votes