Рубрики

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

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

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

C ++

// C ++ программа для печати всех простых факторов
#include <bits/stdc++.h>

using namespace std;

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

void primeFactors(int n) 

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

    while (n % 2 == 0) 

    

        cout << 2 << " "

        n = n/2; 

    

  

    // n должно быть нечетным в этой точке. Так что мы можем пропустить

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

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

    

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

        while (n % i == 0) 

        

            cout << i << " "

            n = n/i; 

        

    

  

    // Это условие для обработки случая, когда n

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

    if (n > 2) 

        cout << n << " "

  
/ * Код водителя * /

int main() 

    int n = 315; 

    primeFactors(n); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// Программа для печати всех основных факторов
# include <stdio.h>
# include <math.h>

  
// Функция для печати всех простых множителей заданного числа n

void primeFactors(int n)

{

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

    while (n%2 == 0)

    {

        printf("%d ", 2);

        n = n/2;

    }

  

    // n должно быть нечетным в этой точке. Так что мы можем пропустить

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

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

    {

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

        while (n%i == 0)

        {

            printf("%d ", i);

            n = n/i;

        }

    }

  

    // Это условие для обработки случая, когда n

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

    if (n > 2)

        printf ("%d ", n);

}

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

int main()

{

    int n = 315;

    primeFactors(n);

    return 0;

}

Джава

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

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);

    }

}

питон

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

  

import math

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

def primeFactors(n):

      

    # Вывести число двух, которые делят 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

C #

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

using System;

  

namespace prime

{

public class GFG

{     

                  

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

    // факторы заданного числа n

    public static void primeFactors(int n)

    {

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

        while (n % 2 == 0)

        {

            Console.Write(2 + " ");

            n /= 2;

        }

  

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

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

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

        {

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

            while (n % i == 0)

            {

                Console.Write(i + " ");

                n /= i;

            }

        }

  

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

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

        if (n > 2)

            Console.Write(n);

    }

      

    // Код драйвера

    public static void Main()

    {

        int n = 315;

        primeFactors(n);

    }

  

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP Эффективная программа для печати всех
// простые факторы заданного числа

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

function primeFactors($n)

{

      

    // Вывести номер

    // 2, которые делят n

    while($n % 2 == 0)

    {

        echo 2," ";

        $n = $n / 2;

    }

  

    // n должно быть нечетным

    // точка. Так что мы можем пропустить

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

    for ($i = 3; $i <= sqrt($n); 

                   $i = $i + 2)

    {

          

        // Пока я делю n,

        // выводим i и делим n

        while ($n % $i == 0)

        {

            echo $i," ";

            $n = $n / $i;

        }

    }

  

    // Это условие

    // обрабатываем случай, когда n

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

    // чем 2

    if ($n > 2)

        echo $n," ";

}

  

    // Код драйвера

    $n = 315;

    primeFactors($n);

  
// Этот код предоставлен aj_36
?>


Выход:

3 3 5 7

Как это работает?
Шаги 1 и 2 относятся к составным числам, а шаг 3 — к простым числам. Чтобы доказать, что полный алгоритм работает, нам нужно доказать, что шаги 1 и 2 действительно заботятся о составных числах. Это ясно, что шаг 1 заботится о четных числах. И после шага 1 все оставшиеся простые множители должны быть нечетными (разница двух простых множителей должна быть не менее 2), это объясняет, почему i увеличивается на 2.
Теперь основная часть состоит в том, что цикл работает до корня квадратного из n, а не до 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 или простому числу.

Связанная статья:
Prime Factorization с использованием Sieve O (log n) для нескольких запросов

Спасибо Вишвасу Гаргу за предложенный выше алгоритм. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

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

0.00 (0%) 0 votes