Dados dos números n y k, imprima el k-ésimo factor primo entre todos los factores primos de n. Por ejemplo, si el número de entrada es 15 y k es 2, entonces la salida debe ser «5». Y si k es 3, entonces la salida debería ser «-1» (hay menos de k factores primos).
Ejemplos :
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
Una solución simple es encontrar primero los factores primos de n. Al encontrar factores primos, no pierda de vista la cuenta. Si la cuenta se convierte en k, devolvemos el factor primo actual.
C++
// Program to print kth prime factor
# include<bits/stdc++.h>
using namespace std;
// A function to generate prime factors of a
// given number n and return k-th prime factor
int kPrimeFactor(int n, int k)
{
// Find the number of 2's that divide k
while (n%2 == 0)
{
k--;
n = n/2;
if (k == 0)
return 2;
}
// n must be odd at this point. So we can skip
// one element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i = i+2)
{
// While i divides n, store i and divide n
while (n%i == 0)
{
if (k == 1)
return i;
k--;
n = n/i;
}
}
// This condition is to handle the case where
// n is a prime number greater than 2
if (n > 2 && k == 1)
return n;
return -1;
}
// Driver Program
int main()
{
int n = 12, k = 3;
cout << kPrimeFactor(n, k) << endl;
n = 14, k = 3;
cout << kPrimeFactor(n, k) << endl;
return 0;
}
Java
// JAVA Program to print kth prime factor
import java.io.*;
import java.math.*;
class GFG{
// A function to generate prime factors
// of a given number n and return k-th
// prime factor
static int kPrimeFactor(int n, int k)
{
// Find the number of 2's that
// divide k
while (n % 2 == 0)
{
k--;
n = n / 2;
if (k == 0)
return 2;
}
// n must be odd at this point.
// So we can skip one element
// (Note i = i +2)
for (int i = 3; i <= Math.sqrt(n); i = i + 2)
{
// While i divides n, store i
// and divide n
while (n % i == 0)
{
if (k == 1)
return i;
k--;
n = n / i;
}
}
// This condition is to handle the
// case where n is a prime number
// greater than 2
if (n > 2 && k == 1)
return n;
return -1;
}
// Driver Program
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));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Python Program to print kth prime factor import math # A function to generate prime factors of a # given number n and return k-th prime factor def kPrimeFactor(n,k) : # Find the number of 2's that divide k while (n % 2 == 0) : k = k - 1 n = n // 2 if (k == 0) : return 2 # n must be odd at this point. So we can # skip one element (Note i = i +2) i = 3 while i <= math.sqrt(n) : # While i divides n, store i and divide n while (n % i == 0) : if (k == 1) : return i k = k - 1 n = n // i i = i + 2 # This condition is to handle the case # where n is a prime number greater than 2 if (n > 2 and k == 1) : return n return -1 # Driver Program n = 12 k = 3 print(kPrimeFactor(n, k)) n = 14 k = 3 print(kPrimeFactor(n, k)) # This code is contributed by Nikita Tiwari.
C#
// C# Program to print kth prime factor.
using System;
class GFG {
// A function to generate prime factors
// of a given number n and return k-th
// prime factor
static int kPrimeFactor(int n, int k)
{
// Find the number of 2's that
// divide k
while (n % 2 == 0)
{
k--;
n = n / 2;
if (k == 0)
return 2;
}
// n must be odd at this point.
// So we can skip one element
// (Note i = i +2)
for (int i = 3; i <= Math.Sqrt(n);
i = i + 2)
{
// While i divides n, store i
// and divide n
while (n % i == 0)
{
if (k == 1)
return i;
k--;
n = n / i;
}
}
// This condition is to handle the
// case where n is a prime number
// greater than 2
if (n > 2 && k == 1)
return n;
return -1;
}
// Driver Program
public static void Main()
{
int n = 12, k = 3;
Console.WriteLine(kPrimeFactor(n, k));
n = 14; k = 3;
Console.WriteLine(kPrimeFactor(n, k));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP Program to print kth prime factor
// A function to generate prime
// factors of a given number n
// and return k-th prime factor
function kPrimeFactor($n, $k)
{
// Find the number of 2's
// that divide k
while ($n%2 == 0)
{
$k--;
$n = $n/2;
if ($k == 0)
return 2;
}
// n must be odd at this point.
// So we can skip one element
// (Note i = i +2)
for($i = 3; $i <= sqrt($n); $i = $i+2)
{
// While i divides n,
// store i and divide n
while ($n % $i == 0)
{
if ($k == 1)
return $i;
$k--;
$n = $n / $i;
}
}
// This condition is to
// handle the case where
// n is a prime number
// greater than 2
if ($n > 2 && $k == 1)
return $n;
return -1;
}
// Driver Code
{
$n = 12;
$k = 3;
echo kPrimeFactor($n, $k),"\n" ;
$n = 14;
$k = 3;
echo kPrimeFactor($n, $k) ;
return 0;
}
// This code contributed by nitin mittal.
?>
Javascript
<script>
// Javascript Program to print kth prime factor
// A function to generate prime factors
// of a given number n and return k-th
// prime factor
function kPrimeFactor(n, k)
{
// Find the number of 2's that
// divide k
while (n % 2 == 0)
{
k--;
n = n / 2;
if (k == 0)
return 2;
}
// n must be odd at this point.
// So we can skip one element
// (Note i = i +2)
for (let i = 3; i <= Math.sqrt(n); i = i + 2)
{
// While i divides n, store i
// and divide n
while (n % i == 0)
{
if (k == 1)
return i;
k--;
n = n / i;
}
}
// This condition is to handle the
// case where n is a prime number
// greater than 2
if (n > 2 && k == 1)
return n;
return -1;
}
// Driver code
let n = 12, k = 3;
document.write(kPrimeFactor(n, k) + "<br/>");
n = 14; k = 3;
document.write(kPrimeFactor(n, k));
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
3 -1
Complejidad de Tiempo: O(√n log n)
Espacio Auxiliar: O(1)
Una Solución Eficiente es usar Tamiz de Eratóstenes. Tenga en cuenta que esta solución es eficiente cuando necesitamos k-ésimo factor primo para múltiples casos de prueba. Para un solo caso, el enfoque anterior es mejor.
La idea es realizar un preprocesamiento y almacenar el factor primo mínimo de todos los números en un rango dado. Una vez que tenemos los factores primos mínimos almacenados en una array, podemos encontrar el factor primo k-ésimo dividiendo repetidamente n con el factor primo mínimo mientras es divisible, y luego repitiendo el proceso para n reducido.
C++
// C++ program to find k-th prime factor using Sieve Of
// Eratosthenes. This program is efficient when we have
// a range of numbers.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 10001;
// Using SieveOfEratosthenes to find smallest prime
// factor of all the numbers.
// For example, if MAX is 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[])
{
// Create a boolean array "prime[0..MAX]" and
// initialize all entries in it as false.
vector <bool> prime(MAX+1, false);
// Initializing smallest factor equal to 2
// for all the even numbers
for (int i=2; i<=MAX; i+=2)
s[i] = 2;
// For odd numbers less than equal to n
for (int i=3; i<=MAX; i+=2)
{
if (prime[i] == false)
{
// s(i) for a prime is the number itself
s[i] = i;
// For all multiples of current prime number
for (int j=i; j*i<=MAX; j+=2)
{
if (prime[i*j] == false)
{
prime[i*j] = true;
// i is the smallest prime factor for
// number "i*j".
s[i*j] = i;
}
}
}
}
}
// Function to generate prime factors and return its
// k-th prime factor. s[i] stores least prime factor
// of i.
int kPrimeFactor(int n, int k, int s[])
{
// Keep dividing n by least prime factor while
// either n is not 1 or count of prime factors
// is not k.
while (n > 1)
{
if (k == 1)
return s[n];
// To keep track of count of prime factors
k--;
// Divide n to find next prime factor
n /= s[n];
}
return -1;
}
// Driver Program
int main()
{
// s[i] is going to store prime factor
// of 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
// Java program to find k-th prime factor
// using Sieve Of Eratosthenes. This
// program is efficient when we have
// a range of numbers.
class GFG
{
static int MAX = 10001;
// Using SieveOfEratosthenes to find smallest prime
// factor of all the numbers.
// For example, if MAX is 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)
{
// Create a boolean array "prime[0..MAX]" and
// initialize all entries in it as false.
boolean[] prime=new boolean[MAX+1];
// Initializing smallest factor equal to 2
// for all the even numbers
for (int i = 2; i <= MAX; i += 2)
s[i] = 2;
// For odd numbers less then equal to n
for (int i = 3; i <= MAX; i += 2)
{
if (prime[i] == false)
{
// s(i) for a prime is the number itself
s[i] = i;
// For all multiples of current prime number
for (int j = i; j * i <= MAX; j += 2)
{
if (prime[i * j] == false)
{
prime[i * j] = true;
// i is the smallest prime factor for
// number "i*j".
s[i * j] = i;
}
}
}
}
}
// Function to generate prime factors
// and return its k-th prime factor.
// s[i] stores least prime factor of i.
static int kPrimeFactor(int n, int k, int []s)
{
// Keep dividing n by least
// prime factor while either
// n is not 1 or count of
// prime factors is not k.
while (n > 1)
{
if (k == 1)
return s[n];
// To keep track of count of prime factors
k--;
// Divide n to find next prime factor
n /= s[n];
}
return -1;
}
// Driver code
public static void main (String[] args)
{
// s[i] is going to store prime factor
// of 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));
}
}
// This code is contributed by mits
Python3
# python3 program to find k-th prime factor using Sieve Of # Eratosthenes. This program is efficient when we have # a range of numbers. MAX = 10001 # Using SieveOfEratosthenes to find smallest prime # factor of all the numbers. # For example, if MAX is 10, # s[2] = s[4] = s[6] = s[10] = 2 # s[3] = s[9] = 3 # s[5] = 5 # s[7] = 7 def sieveOfEratosthenes(s): # Create a boolean array "prime[0..MAX]" and # initialize all entries in it as false. prime=[False for i in range(MAX+1)] # Initializing smallest factor equal to 2 # for all the even numbers for i in range(2,MAX+1,2): s[i] = 2; # For odd numbers less then equal to n for i in range(3,MAX,2): if (prime[i] == False): # s(i) for a prime is the number itself s[i] = i # For all multiples of current prime number for j in range(i,MAX+1,2): if j*j> MAX: break if (prime[i*j] == False): prime[i*j] = True # i is the smallest prime factor for # number "i*j". s[i*j] = i # Function to generate prime factors and return its # k-th prime factor. s[i] stores least prime factor # of i. def kPrimeFactor(n, k, s): # Keep dividing n by least prime factor while # either n is not 1 or count of prime factors # is not k. while (n > 1): if (k == 1): return s[n] # To keep track of count of prime factors k-=1 # Divide n to find next prime factor n //= s[n] return -1 # Driver Program # s[i] is going to store prime factor # of 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)) # This code is contributed by mohit kumar 29
C#
// C# program to find k-th prime factor
// using Sieve Of Eratosthenes. This
// program is efficient when we have
// a range of numbers and we
using System;
class GFG
{
static int MAX = 10001;
// Using SieveOfEratosthenes to find
// smallest prime factor of all the
// numbers. For example, if MAX is 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)
{
// Create a boolean array "prime[0..MAX]"
// and initialize all entries in it as false.
bool[] prime = new bool[MAX + 1];
// Initializing smallest factor equal
// to 2 for all the even numbers
for (int i = 2; i <= MAX; i += 2)
s[i] = 2;
// For odd numbers less then equal to n
for (int i = 3; i <= MAX; i += 2)
{
if (prime[i] == false)
{
// s(i) for a prime is the
// number itself
s[i] = i;
// For all multiples of current
// prime number
for (int j = i; j * i <= MAX; j += 2)
{
if (prime[i * j] == false)
{
prime[i * j] = true;
// i is the smallest prime factor
// for number "i*j".
s[i * j] = i;
}
}
}
}
}
// Function to generate prime factors
// and return its k-th prime factor.
// s[i] stores least prime factor of i.
static int kPrimeFactor(int n, int k, int []s)
{
// Keep dividing n by least prime
// factor while either n is not 1
// or count of prime factors is not k.
while (n > 1)
{
if (k == 1)
return s[n];
// To keep track of count of
// prime factors
k--;
// Divide n to find next prime factor
n /= s[n];
}
return -1;
}
// Driver Code
static void Main()
{
// s[i] is going to store prime
// factor of 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));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to find k-th prime factor
// using Sieve Of Eratosthenes. This program
// is efficient when we have a range of numbers.
$MAX = 10001;
// Using SieveOfEratosthenes to find
// smallest prime factor of all the numbers.
// For example, if MAX is 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;
// Create a boolean array "prime[0..MAX]"
// and initialize all entries in it as false.
$prime = array_fill(0, $MAX + 1, false);
// Initializing smallest factor equal
// to 2 for all the even numbers
for ($i = 2; $i <= $MAX; $i += 2)
$s[$i] = 2;
// For odd numbers less then equal to n
for ($i = 3; $i <= $MAX; $i += 2)
{
if ($prime[$i] == false)
{
// s(i) for a prime is the
// number itself
$s[$i] = $i;
// For all multiples of current
// prime number
for ($j = $i; $j * $i <= $MAX; $j += 2)
{
if ($prime[$i * $j] == false)
{
$prime[$i * $j] = true;
// i is the smallest prime
// factor for number "i*j".
$s[$i * $j] = $i;
}
}
}
}
}
// Function to generate prime factors and
// return its k-th prime factor. s[i] stores
// least prime factor of i.
function kPrimeFactor($n, $k, $s)
{
// Keep dividing n by least prime
// factor while either n is not 1
// or count of prime factors is not k.
while ($n > 1)
{
if ($k == 1)
return $s[$n];
// To keep track of count of
// prime factors
$k--;
// Divide n to find next prime factor
$n = (int)($n / $s[$n]);
}
return -1;
}
// Driver Code
// s[i] is going to store prime
// factor of 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));
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// Javascript program to find k-th prime factor
// using Sieve Of Eratosthenes. This
// program is efficient when we have
// a range of numbers.
var MAX = 10001;
// Using SieveOfEratosthenes to find smallest prime
// factor of all the numbers.
// For example, if MAX is 10,
// s[2] = s[4] = s[6] = s[10] = 2
// s[3] = s[9] = 3
// s[5] = 5
// s[7] = 7
function sieveOfEratosthenes(s)
{
// Create a boolean array "prime[0..MAX]" and
// initialize all entries in it as false.
prime=Array.from({length: MAX+1}, (_, i) => false);
// Initializing smallest factor equal to 2
// for all the even numbers
for (i = 2; i <= MAX; i += 2)
s[i] = 2;
// For odd numbers less then equal to n
for (i = 3; i <= MAX; i += 2)
{
if (prime[i] == false)
{
// s(i) for a prime is the number itself
s[i] = i;
// For all multiples of current prime number
for (j = i; j * i <= MAX; j += 2)
{
if (prime[i * j] == false)
{
prime[i * j] = true;
// i is the smallest prime factor for
// number "i*j".
s[i * j] = i;
}
}
}
}
}
// Function to generate prime factors
// and return its k-th prime factor.
// s[i] stores least prime factor of i.
function kPrimeFactor(n , k , s)
{
// Keep dividing n by least
// prime factor while either
// n is not 1 or count of
// prime factors is not k.
while (n > 1)
{
if (k == 1)
return s[n];
// To keep track of count of prime factors
k--;
// Divide n to find next prime factor
n /= s[n];
}
return -1;
}
// Driver code
// s[i] is going to store prime factor
// of i.
var s = Array.from({length: MAX + 1}, (_, i) => 0);
sieveOfEratosthenes(s);
var n = 12, k = 3;
document.write(kPrimeFactor(n, k, s)+"<br>");
n = 14;
k = 3;
document.write(kPrimeFactor(n, k, s));
// This code contributed by shikhasingrajput
</script>
Producción:
3 -1
Complejidad de tiempo: O(n*log(log(n)))
Espacio auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi y Afzal Ansari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA