Рубрики

Распечатать все основные факторы и их силы

Учитывая число N, выведите все его уникальные простые множители и их степени в N.
Примеры:

Input: N = 100
Output: Factor Power
          2      2
          5      2

Input: N = 35
Output: Factor  Power
          5      1
          7      1

Простое решение — сначала найти простые множители N. Затем для каждого простого множителя найдите его наибольшую степень, которая делит N, и выведите его.

Эффективным решением является использование сита эратосфена .

1) First compute an array s[N+1] using Sieve of Eratosthenes.

s[i] = Smallest prime factor of "i" that
       divides "i".

For example let N  = 10
  s[2] = s[4] = s[6] = s[8] = s[10] = 2;
  s[3] = s[9] = 3;
  s[5] = 5;
  s[7] = 7;


2) Using the above computed array s[],
   we can find all powers in O(Log N) time.

    curr = s[N];  // Current prime factor of N
    cnt = 1;   // Power of current prime factor

    // Printing prime factors and their powers
    while (N > 1)
    {
        N /= s[N];

        // N is now N/s[N].  If new N also has its 
        // smallest prime factor as curr, increment 
        // power and continue
        if (curr == s[N])
        {
            cnt++;
            continue;
        }

        // Print prime factor and its power
        print(curr, cnt);

        // Update current prime factor as s[N] and
        // initializing count as 1.
        curr = s[N];
        cnt = 1;
    }

Ниже приведена реализация вышеуказанных шагов.

C ++

// C ++ Программа для печати простых факторов и их
// полномочия, использующие Сито Эратосфена
#include<bits/stdc++.h>

using namespace std;

  
// Использование SieveOfEratosthenes для поиска наименьшего простого числа
// фактор всех чисел.
// Например, если N равно 10,
// s [2] = s [4] = s [6] = s [10] = 2
// s [3] = s [9] = 3
// s [5] = 5
// s [7] = 7

void sieveOfEratosthenes(int N, int s[])

{

    // Создаем логический массив "prime [0..n]" и

    // инициализируем все записи в нем как ложные.

    vector <bool> prime(N+1, false);

  

    // Инициализация наименьшего фактора, равного 2

    // для всех чётных чисел

    for (int i=2; i<=N; i+=2)

        s[i] = 2;

  

    // Для нечетных чисел меньше чем равно n

    for (int i=3; i<=N; i+=2)

    {

        if (prime[i] == false)

        {

            // s (i) для простого числа - это само число

            s[i] = i;

  

            // Для всех кратных текущего простого числа

            for (int j=i; j*i<=N; j+=2)

            {

                if (prime[i*j] == false)

                {

                    prime[i*j] = true;

  

                    // я наименьший простой фактор для

                    // число "i * j".

                    s[i*j] = i;

                }

            }

        }

    }

}

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

void generatePrimeFactors(int N)

{

    // s [i] будет хранить наименьший простой фактор

    // из я.

    int s[N+1];

  

    // Заполняем значения в s [] используя sieve

    sieveOfEratosthenes(N, s);

  

    printf("Factor Power\n");

  

    int curr = s[N];  // Текущий простой фактор N

    int cnt = 1;   // Сила текущего простого множителя

  

    // Печать основных факторов и их возможностей

    while (N > 1)

    {

        N /= s[N];

  

        // N теперь N / s [N]. Если новый N als имеет наименьшее

        // простой множитель как curr, приращение мощности

        if (curr == s[N])

        {

            cnt++;

            continue;

        }

  

        printf("%d\t%d\n", curr, cnt);

  

        // Обновляем текущий простой множитель как s [N] и

        // инициализация считать как 1.

        curr = s[N];

        cnt = 1;

    }

}

  
// Программа для водителя

int main()

{

    int N = 360;

    generatePrimeFactors(N);

    return 0;

}

Джава

// Java-программа для печати премьер
// факторы и их возможности использования
// Сито Эратосфена

class GFG

{
// Использование SieveOfEratosthenes
// найти наименьшее простое число
// фактор всех чисел.
// Например, если N равно 10,
// s [2] = s [4] = s [6] = s [10] = 2
// s [3] = s [9] = 3
// s [5] = 5
// s [7] = 7

static void sieveOfEratosthenes(int N, 

                                int s[])

{

    // Создать логический массив

    // "prime [0..n]" и инициализируем

    // все записи в нем как ложные.

    boolean[] prime = new boolean[N + 1];

  

    // Инициализация наименьшего

    // коэффициент равен 2

    // для всех чётных чисел

    for (int i = 2; i <= N; i += 2)

        s[i] = 2;

  

    // Для нечетных чисел меньше

    // тогда равно n

    for (int i = 3; i <= N; i += 2)

    {

        if (prime[i] == false)

        {

            // s (i) для простого числа

            // сам номер

            s[i] = i;

  

            // Для всех кратных

            // текущее простое число

            for (int j = i; j * i <= N; j += 2)

            {

                if (prime[i * j] == false)

                {

                    prime[i * j] = true;

  

                    // я наименьшее простое число

                    // фактор для числа "i * j".

                    s[i * j] = i;

                }

            }

        }

    }

}

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

static void generatePrimeFactors(int N)

{

    // s [i] собирается хранить

    // наименьший простой фактор i.

    int[] s = new int[N + 1];

  

    // Заполняем значения в s [] используя sieve

    sieveOfEratosthenes(N, s);

  

    System.out.println("Factor Power");

  

    int curr = s[N]; // Текущий простой фактор N

    int cnt = 1; // Сила текущего простого множителя

  

    // Печать основных факторов

    // и их полномочия

    while (N > 1)

    {

        N /= s[N];

  

        // N теперь N / s [N]. Если новый N

        // также имеет наименьшее простое число

        // фактор как curr, приращение мощности

        if (curr == s[N])

        {

            cnt++;

            continue;

        }

  

        System.out.println(curr + "\t" + cnt);

  

        // Обновление текущего простого множителя

        // как s [N] и инициализация

        // считать как 1.

        curr = s[N];

        cnt = 1;

    }

}

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

public static void main(String[] args)

{

    int N = 360;

    generatePrimeFactors(N);

}
}

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

python3

# Python3 программа для печати премьер
# факторы и их полномочия
# Сито Эратосфена

  
# Использование SieveOfEratosthenes для
# найти наименьший простой фактор
# всех чисел.

  
# Например, если N равно 10,
# s [2] = s [4] = s [6] = s [10] = 2
# s [3] = s [9] = 3
# s [5] = 5
# s [7] = 7

def sieveOfEratosthenes(N, s):

      

    # Создать логический массив

    # "Prime [0..n]" и инициализировать

    # все записи в нем как ложные.

    prime = [False] * (N+1)

  

    # Инициализация наименьшего фактора

    # равно 2 для всех четных

    # числа

    for i in range(2, N+1, 2): 

        s[i] = 2

  

    # Для нечетных чисел меньше, чем

    # равно n

    for i in range(3, N+1, 2):

        if (prime[i] == False):

              

            # s (i) для простого числа

            # сам номер

            s[i] = i

  

            # Для всех кратных

            # текущий простой номер

            for j in range(i, int(N / i) + 1, 2):

                if (prime[i*j] == False):

                    prime[i*j] = True

  

                    # я самый маленький

                    # главный фактор для

                    # число "i * j".

                    s[i * j] = i

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

def generatePrimeFactors(N):

  

    # s [i] собирается хранить

    # наименьший простой фактор

    # из я.

    s = [0] * (N+1)

  

    # Заполнение значений в с []

    # используя сито

    sieveOfEratosthenes(N, s)

  

    print("Factor Power")

  

    # Текущий простой фактор N

    curr = s[N]

      

    # Мощность текущего простого множителя

    cnt = 1 

  

    # Печать основных факторов и

    # их полномочия

    while (N > 1):

        N //= s[N]

  

        # N теперь N / s [N]. Если новый N

        # als имеет наименьшее простое число

        # фактор как курс, приращение

        # мощность

        if (curr == s[N]):

            cnt += 1

            continue

  

        print(str(curr) + "\t" + str(cnt))

  

        # Обновление текущего простого множителя

        # as s [N] и инициализация

        # считается как 1.

        curr = s[N]

        cnt = 1

  
# Водительская программа

N = 360

generatePrimeFactors(N)

  
# Этот код предоставлен Ансу Кумари

C #

// C # Программа для печати премьер
// факторы и их возможности использования
// Сито Эратосфена

class GFG

{
// Использование SieveOfEratosthenes
// найти наименьшее простое число
// фактор всех чисел.
// Например, если N равно 10,
// s [2] = s [4] = s [6] = s [10] = 2
// s [3] = s [9] = 3
// s [5] = 5
// s [7] = 7

static void sieveOfEratosthenes(int N, int[] s)

{

    // Создать логический массив

    // "prime [0..n]" и инициализируем

    // все записи в нем как ложные.

    bool[] prime = new bool[N + 1];

  

    // Инициализация наименьшего

    // коэффициент равен 2

    // для всех чётных чисел

    for (int i = 2; i <= N; i += 2)

        s[i] = 2;

  

    // Для нечетных чисел меньше

    // тогда равно n

    for (int i = 3; i <= N; i += 2)

    {

        if (prime[i] == false)

        {

            // s (i) для простого числа

            // сам номер

            s[i] = i;

  

            // Для всех кратных

            // текущее простое число

            for (int j = i; j * i <= N; j += 2)

            {

                if (prime[i * j] == false)

                {

                    prime[i * j] = true;

  

                    // я наименьшее простое число

                    // фактор для числа "i * j".

                    s[i * j] = i;

                }

            }

        }

    }

}

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

static void generatePrimeFactors(int N)

{

    // s [i] собирается хранить

    // наименьший простой фактор i.

    int[] s = new int[N + 1];

  

    // Заполняем значения в s [] используя sieve

    sieveOfEratosthenes(N, s);

  

    System.Console.WriteLine("Factor Power");

  

    int curr = s[N]; // Текущий простой фактор N

    int cnt = 1; // Сила текущего простого множителя

  

    // Печать основных факторов

    // и их полномочия

    while (N > 1)

    {

        N /= s[N];

  

        // N теперь N / s [N]. Если новый N

        // также имеет наименьшее простое число

        // фактор как curr, приращение мощности

        if (curr == s[N])

        {

            cnt++;

            continue;

        }

  

        System.Console.WriteLine(curr + "\t" + cnt);

  

        // Обновление текущего простого множителя

        // как s [N] и инициализация

        // считать как 1.

        curr = s[N];

        cnt = 1;

    }

}

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

static void Main()

{

    int N = 360;

    generatePrimeFactors(N);

}
}

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

PHP

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

  
// Использование SieveOfEratosthenes для поиска наименьшего
// главный фактор всех чисел.
// Например, если N равно 10,
// s [2] = s [4] = s [6] = s [10] = 2
// s [3] = s [9] = 3
// s [5] = 5
// s [7] = 7

function sieveOfEratosthenes($N, &$s)

{

    // Создаем логический массив "prime [0..n]" и

    // инициализируем все записи в нем как ложные.

    $prime = array_fill(0, $N + 1, false);

  

    // Инициализация наименьшего фактора равна

    // в 2 для всех четных чисел

    for ($i = 2; $i <= $N; $i += 2)

        $s[$i] = 2;

  

    // Для нечетных чисел меньше чем равно n

    for ($i = 3; $i <= $N; $i += 2)

    {

        if ($prime[$i] == false)

        {

            // s (i) для простого числа

            // сам номер

            $s[$i] = $i;

  

            // Для всех кратных текущего

            // простое число

            for ($j = $i; $j * $i <= $N; $j += 2)

            {

                if ($prime[$i * $j] == false)

                {

                    $prime[$i * $j] = true;

  

                    // я наименьший простой фактор

                    // для номера "i * j".

                    $s[$i * $j] = $i;

                }

            }

        }

    }

}

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

function generatePrimeFactors($N)

{

    // s [i] собирается хранить наименьшее

    // главный фактор i.

    $s = array_fill(0, $N + 1, 0);

  

    // Заполняем значения в s [] используя сито

    sieveOfEratosthenes($N, $s);

  

    print("Factor Power\n");

  

    $curr = $s[$N]; // Текущий простой фактор N

    $cnt = 1; // Сила текущего простого множителя

  

    // Печать основных факторов и их возможностей

    while ($N > 1)

    {

        if($s[$N])

        $N = (int)($N / $s[$N]);

  

        // N теперь N / s [N]. Если новый N als имеет наименьшее

        // простой множитель как curr, приращение мощности

        if ($curr == $s[$N])

        {

            $cnt++;

            continue;

        }

  

        print($curr . "\t" . $cnt . "\n");

  

        // Обновляем текущий простой множитель как s [N]

        // и инициализация считать как 1.

        $curr = $s[$N];

        $cnt = 1;

    }

}

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

$N = 360;

generatePrimeFactors($N);

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

Выход:

Factor  Power
  2      3
  3      2
  5      1

Вышеприведенный алгоритм находит все степени за O (Log N) после того, как мы заполнили s []. Это может быть очень полезно в конкурентной среде, где у нас есть верхний предел, и нам нужно вычислить основные факторы и их мощность для многих тестовых случаев. В этом случае массив должен быть заполнен s [] только один раз.

Эта статья предоставлена Рахул Агравал . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Распечатать все основные факторы и их силы

0.00 (0%) 0 votes