Рубрики

k-й простой множитель заданного числа

Учитывая два числа n и k, выведите k-й простой множитель среди всех простых факторов n. Например, если входное число равно 15, а k равно 2, то выходное значение должно быть «5». И если k равно 3, то выходное значение должно быть «-1» (число простых коэффициентов меньше k).

Примеры :

Input : n = 225, k = 2        
Output : 3
Prime factors are 3 3 5 5. Second
prime factor is 3.

Input : n = 81, k = 5
Output : -1
Prime factors are 3 3 3 3

Простое решение — сначала найти простые множители n. Находя главные факторы, следите за количеством. Если count становится k, мы возвращаем текущий простой множитель.

C ++

// Программа для вывода k-го простого множителя
# include<bits/stdc++.h>

using namespace std;

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

int kPrimeFactor(int n, int k)

{

    // Находим число 2, которые делят k

    while (n%2 == 0)

    {

        k--;

        n = n/2;

        if (k == 0)

         return 2;

    }

  

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

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

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

    {

        // Пока я делю n, сохраняем i и делим n

        while (n%i == 0)

        {

            if (k == 1)

              return i;

  

            k--;

            n = n/i;

        }

    }

  

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

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

    if (n > 2 && k == 1)

        return n;

  

    return -1;

}

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

int main()

{

    int n = 12, k = 3;

    cout << kPrimeFactor(n, k) << endl;

    n = 14, k = 3;

    cout << kPrimeFactor(n, k) << endl;

    return 0;

}

Джава

// JAVA программа для печати k-го простого множителя

import java.io.*;

import java.math.*;

  

class GFG{

      

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

    // заданного числа n и возврата k-го

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

    static int kPrimeFactor(int n, int k)

    {

        // Находим число 2, которое

        // делим k

        while (n % 2 == 0)

        {

            k--;

            n = n / 2;

            if (k == 0)

             return 2;

        }

       

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

        // Таким образом, мы можем пропустить один элемент

        // (Примечание i = i +2)

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

        {

            // Пока я делю n, сохраняю

            // и делим n

            while (n % i == 0)

            {

                if (k == 1)

                  return i;

       

                k--;

                n = n / i;

            }

        }

       

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

        // случай, когда n - простое число

        // больше 2

        if (n > 2 && k == 1)

            return n;

       

        return -1;

    }

       

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

    public static void main(String args[])

    {

        int n = 12, k = 3;

        System.out.println(kPrimeFactor(n, k));

        n = 14; k = 3;

        System.out.println(kPrimeFactor(n, k));

    }

}

  
/ * Этот код предоставлен Никитой Тивари. * /

питон

# Программа Python для вывода k-го простого множителя

import math

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

def kPrimeFactor(n,k) :

  

    # Найдите число 2, которые делят k

    while (n % 2 == 0) :

        k = k - 1

        n = n / 2

        if (k == 0) :

            return 2

   

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

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

    i = 3

    while i <= math.sqrt(n) :

      

        # Пока я делю n, сохраняю i и делю n

        while (n % i == 0) :

            if (k == 1) :

                return i

   

            k = k - 1

            n = n / i

          

        i = i + 2

   

    # Это условие для обработки дела

    # где n простое число больше 2

    if (n > 2 and k == 1) :

        return n

   

    return -1

  
# Драйверная программа

n = 12

k = 3

print(kPrimeFactor(n, k))

  

n = 14

k = 3

print(kPrimeFactor(n, k))

  
# Этот код предоставлен Никитой Тивари.

C #

// C # Программа для вывода k-го простого множителя.

using System;

  

class GFG {

      

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

    // заданного числа n и возврата k-го

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

    static int kPrimeFactor(int n, int k)

    {

          

        // Находим число 2, которое

        // делим k

        while (n % 2 == 0)

        {

            k--;

            n = n / 2;

              

            if (k == 0)

                return 2;

        }

      

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

        // Таким образом, мы можем пропустить один элемент

        // (Примечание i = i +2)

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

                                i = i + 2)

        {

              

            // Пока я делю n, сохраняю

            // и делим n

            while (n % i == 0)

            {

                if (k == 1)

                    return i;

      

                k--;

                n = n / i;

            }

        }

      

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

        // случай, когда n - простое число

        // больше 2

        if (n > 2 && k == 1)

            return n;

      

        return -1;

    }

      

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

    public static void Main()

    {

          

        int n = 12, k = 3;

        Console.WriteLine(kPrimeFactor(n, k));

          

        n = 14; k = 3;

        Console.WriteLine(kPrimeFactor(n, k));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Программа PHP для вывода k-го простого множителя

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

function kPrimeFactor($n, $k)

{

      

    // Находим число 2

    // это делит k

    while ($n%2 == 0)

    {

        $k--;

        $n = $n/2;

        if ($k == 0)

        return 2;

    }

  

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

    // Таким образом, мы можем пропустить один элемент

    // (Примечание i = i +2)

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

    {

          

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

        // сохраняем i и делим n

        while ($n % $i == 0)

        {

            if ($k == 1)

            return $i;

  

            $k--;

            $n = $n / $i;

        }

    }

  

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

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

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

    // больше 2

    if ($n > 2 && $k == 1)

        return $n;

  

    return -1;

}

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

    $n = 12; 

    $k = 3;

    echo kPrimeFactor($n, $k),"\n" ;

    $n = 14;

    $k = 3;

    echo kPrimeFactor($n, $k) ;

    return 0;

}

  
// Этот код предоставлен нитин митталь.
?>


Выход:

3
-1

Эффективным решением является использование сита эратосфена. Обратите внимание, что это решение эффективно, когда нам нужен k-й простой множитель для нескольких тестовых случаев. Для одного случая предыдущий подход лучше.
Идея состоит в том, чтобы сделать предварительную обработку и сохранить наименьший простой фактор всех чисел в данном диапазоне. Как только у нас есть наименьшие простые множители, хранящиеся в массиве, мы можем найти k-й простой множитель, многократно разделив n с наименьшим простым множителем, пока он делится, а затем повторить процесс для уменьшенного n.

C ++

// C ++ программа для поиска k-го простого множителя с использованием Sieve Of
// Эратосфен. Эта программа эффективна, когда у нас есть
// диапазон чисел.
#include<bits/stdc++.h>

  

using namespace std;

const int MAX = 10001;

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

void sieveOfEratosthenes(int s[])

{

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

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

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

  

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

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

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

        s[i] = 2;

  

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

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

    {

        if (prime[i] == false)

        {

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

            s[i] = i;

  

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

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

            {

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

                {

                    prime[i*j] = true;

  

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

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

                    s[i*j] = i;

                }

            }

        }

    }

}

  
// Функция для генерации простых факторов и возврата ее
// k-й простой фактор. s [i] хранит наименьший простой фактор
// из я.

int kPrimeFactor(int n, int k, int s[])

{

    // Продолжаем делить n на наименьший простой множитель, пока

    // либо n не равно 1, либо число простых факторов

    // это не к.

    while (n > 1)

    {

        if (k == 1)

          return s[n];

  

        // Следить за количеством простых факторов

        k--;

  

        // Делим n, чтобы найти следующий простой множитель

        n /= s[n];

    }

  

    return -1;

}

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

int main()

{

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

    // из я.

    int s[MAX+1];

    memset(s, -1, sizeof(s));

    sieveOfEratosthenes(s);

  

    int n = 12, k = 3;

    cout << kPrimeFactor(n, k, s) << endl;

    n = 14, k = 3;

    cout << kPrimeFactor(n, k, s) << endl;

    return 0;

}

Джава

// Java-программа для поиска k-го простого множителя
// используя сито эратосфена. Эта
// программа эффективна, когда мы имеем
// диапазон чисел.

class GFG

{

static int MAX = 10001

  
// Использование SieveOfEratosthenes для поиска наименьшего простого числа
// фактор всех чисел.
// Например, если MAX равен 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 []s) 

      

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

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

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

  

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

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

    for (int i = 2; i <= MAX; i += 2

        s[i] = 2

  

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

    for (int i = 3; i <= MAX; i += 2

    

        if (prime[i] == false

        

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

            s[i] = i; 

  

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

            for (int j = i; j * i <= MAX; j += 2

            

                if (prime[i * j] == false

                

                    prime[i * j] = true

  

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

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

                    s[i * j] = i; 

                

            

        

    

  
// Функция для генерации простых факторов
// и вернуть его k-й простой множитель.
// s [i] хранит наименьший простой множитель i.

static int kPrimeFactor(int n, int k, int []s) 

    // Продолжаем делить п минимум

    // главный фактор, пока либо

    // n не 1 или число

    // простые факторы не к.

    while (n > 1

    

        if (k == 1

        return s[n]; 

  

        // Следить за количеством простых факторов

        k--; 

  

        // Делим n, чтобы найти следующий простой множитель

        n /= s[n]; 

    

    return -1

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

public static void main (String[] args) 

{

      

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

    // из я.

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

    sieveOfEratosthenes(s); 

  

    int n = 12, k = 3

    System.out.println(kPrimeFactor(n, k, s)); 

    n = 14;

    k = 3

    System.out.println(kPrimeFactor(n, k, s)); 


}

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

python3

# python3 программа для поиска k-го простого множителя с помощью Sieve Of
# Эратосфен. Эта программа эффективна, когда у нас есть
# диапазон чисел.

  

MAX = 10001

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

def sieveOfEratosthenes(s):

  
# Создайте логический массив "prime [0..MAX]" и
# инициализировать все записи в нем как ложные.

    prime=[False for i in range(MAX+1)]

  

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

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

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

        s[i] = 2;

  

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

    for i in range(3,MAX,2):

        if (prime[i] == False):

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

            s[i] = i

  

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

            for j in range(i,MAX+1,2):

                if j*j> MAX:

                    break

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

                    prime[i*j] = True

  

                    # я наименьший главный фактор для

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

                    s[i*j] = i

  
# Функция для генерации простых факторов и возврата ее
# k-й главный фактор. s [i] хранит наименьший простой фактор
# из я.

def kPrimeFactor(n, k, s):

    # Продолжайте делить n на множитель

    # либо n не равно 1, либо число простых факторов

    # не к.

    while (n > 1):

  

        if (k == 1):

            return s[n]

  

        # Чтобы вести учет количества основных факторов

        k-=1

  

        # Разделите n, чтобы найти следующий простой фактор

        n //= s[n]

  

  

    return -1

  
# Драйверная программа

  
# s [i] собирается хранить главный фактор
# из я.

s=[-1 for i in range(MAX+1)]

  
sieveOfEratosthenes(s)

  

n = 12

k = 3

print(kPrimeFactor(n, k, s))

  

n = 14

k = 3

print(kPrimeFactor(n, k, s))

  
# Этот код предоставлен mohit kumar 29

C #

// C # программа для поиска k-го простого множителя
// используя сито эратосфена. Эта
// программа эффективна, когда мы имеем
// диапазон чисел и мы

using System;

class GFG

{

static int MAX = 10001; 

  
// Использование SieveOfEratosthenes для поиска
// наименьший простой фактор из всех
// числа. Например, если MAX равен 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 []s) 

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

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

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

  

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

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

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

        s[i] = 2; 

  

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

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

    

        if (prime[i] == false

        

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

            // сам номер

            s[i] = i; 

  

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

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

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

            

                if (prime[i * j] == false

                

                    prime[i * j] = true

  

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

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

                    s[i * j] = i; 

                

            

        

    

  
// Функция для генерации простых факторов
// и вернуть его k-й простой множитель.
// s [i] хранит наименьший простой множитель i.

static int kPrimeFactor(int n, int k, int []s) 

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

    // фактор, пока n не равно 1

    // или число простых факторов не k.

    while (n > 1) 

    

        if (k == 1) 

        return s[n]; 

  

        // Вести подсчет

        // главные факторы

        k--; 

  

        // Делим n, чтобы найти следующий простой множитель

        n /= s[n]; 

    

  

    return -1; 

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

static void Main() 

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

    // фактор я.

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

    sieveOfEratosthenes(s); 

  

    int n = 12, k = 3; 

    Console.WriteLine(kPrimeFactor(n, k, s)); 

    n = 14;

    k = 3; 

    Console.WriteLine(kPrimeFactor(n, k, s)); 


}

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

PHP

<?php
// PHP программа для поиска k-го простого множителя
// используя сито эратосфена. Эта программа
// эффективен, когда у нас есть диапазон чисел.

  

$MAX = 10001;

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

function sieveOfEratosthenes(&$s)

{

    global $MAX;

      

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

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

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

  

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

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

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

        $s[$i] = 2;

  

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

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

    {

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

        {

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

            // сам номер

            $s[$i] = $i;

  

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

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

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

            {

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

                {

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

  

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

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

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

                }

            }

        }

    }

}

  
// Функция для генерации простых факторов и
// вернуть его k-й простой множитель. s [i] магазины
// наименьший простой фактор i.

function kPrimeFactor($n, $k, $s)

{

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

    // фактор, пока n не равно 1

    // или число простых факторов не k.

    while ($n > 1)

    {

        if ($k == 1)

        return $s[$n];

  

        // Вести подсчет

        // главные факторы

        $k--;

  

        // Делим n, чтобы найти следующий простой множитель

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

    }

  

    return -1;

}

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

  
// s [i] собирается хранить премьер
// фактор я.

$s = array_fill(0, $MAX + 1, -1);

sieveOfEratosthenes($s);

  

$n = 12;

$k = 3;

print(kPrimeFactor($n, $k, $s) . "\n");

  

$n = 14;

$k = 3;

print(kPrimeFactor($n, $k, $s));

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

Выход:

3
-1

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

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

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

k-й простой множитель заданного числа

0.00 (0%) 0 votes