N-ésimo factor primo de un número dado

Posted on by Rudeus Greyrat

Dadas las consultas Q que constan de dos enteros, uno es número (1 <= número <= 10 6 ) y el otro es N., la tarea es encontrar el N-ésimo factor primo del número dado. 
Ejemplos: 
 

Entrada: Número de consultas, Q = 4 
número = 6, N = 1 
número = 210, N = 3 
número = 210, N = 2 
número = 60, N = 2
Salida: 
2 
5 
3 
3
6 tiene factores primos 2 y 3
210 tiene factores primos 2, 3 y 6.  60 
tiene factores primos 2 y 3. 
 

Un enfoque ingenuo es factorizar cada número y almacenar los factores primos. Imprime los N-ésimos factores primos así almacenados. 
Complejidad de tiempo: O(log(n)) por consulta. 
Un enfoque eficiente es precalcular todos los factores primos del número y almacenar los números en un orden ordenado en un vector 2-D . Dado que el número no será mayor que 10 6 , el número de factores primos únicos será de alrededor de 7-8 como máximo ( porque 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 >= 10 6 ). Una vez que se almacenan los números, la consulta se puede responder en O (1) ya que el índice n-1 tendrá la respuesta en la fila de números. 
A continuación se muestra la implementación del enfoque anterior: 
 

CPP

// C++ program to answer queries
// for N-th prime factor of a number
#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
 
// 2-D vector that stores prime factors
vector<int> v[N];
 
// Function to pre-store prime
// factors of all numbers till 10^6
void preprocess()
{
    // calculate unique prime factors for
    // every number till 10^6
    for (int i = 1; i < N; i++) {
 
        int num = i;
 
        // find prime factors
        for (int j = 2; j <= sqrt(num); j++) {
            if (num % j == 0) {
 
                // store if prime factor
                v[i].push_back(j);
 
                while (num % j == 0) {
                    num = num / j;
                }
            }
        }
         
        if(num>2)
        v[i].push_back(num);
         
    }
}
 
// Function that returns answer
// for every query
int query(int number, int n)
{
    return v[number][n - 1];
}
 
// Driver Code
int main()
{
 
    // Function to pre-store unique prime factors
    preprocess();
 
    // 1st query
    int number = 6, n = 1;
    cout << query(number, n) << endl;
 
    // 2nd query
    number = 210, n = 3;
    cout << query(number, n) << endl;
 
    // 3rd query
    number = 210, n = 2;
    cout << query(number, n) << endl;
 
    // 4th query
    number = 60, n = 2;
    cout << query(number, n) << endl;
 
    return 0;
}

Java

// Java program to answer queries
// for N-th prime factor of a number
import java.util.*;
 
class GFG
{
     
static int N = 1000001;
 
// 2-D vector that stores prime factors
static Vector<Integer> []v = new Vector[N];
 
// Function to pre-store prime
// factors of all numbers till 10^6
static void preprocess()
{
    // calculate unique prime factors for
    // every number till 10^6
    for (int i = 1; i < N; i++)
    {
 
        int num = i;
 
        // find prime factors
        for (int j = 2; j <= Math.sqrt(num); j++)
        {
            if (num % j == 0)
            {
 
                // store if prime factor
                v[i].add(j);
 
                while (num % j == 0)
                {
                    num = num / j;
                }
            }
        }
        if(num > 2)
        v[i].add(num);
    }
}
 
// Function that returns answer
// for every query
static int query(int number, int n)
{
    return v[number].get(n - 1);
}
 
// Driver Code
public static void main(String[] args)
{
 
    for (int i = 0; i < N; i++)
        v[i] = new Vector<Integer>();
 
    // Function to pre-store unique prime factors
    preprocess();
 
    // 1st query
    int number = 6, n = 1;
    System.out.print(query(number, n) +"\n");
 
    // 2nd query
    number = 210; n = 3;
    System.out.print(query(number, n) +"\n");
 
    // 3rd query
    number = 210; n = 2;
    System.out.print(query(number, n) +"\n");
 
    // 4th query
    number = 60; n = 2;
    System.out.print(query(number, n) +"\n");
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to answer queries
# for N-th prime factor of a number
from math import sqrt,ceil
N = 10001
 
# 2-D vector that stores prime factors
v = [[] for i in range(N)]
 
# Function to pre-store prime
# factors of all numbers till 10^6
def preprocess():
     
    # calculate unique prime factors for
    # every number till 10^6
    for i in range(1, N):
 
        num = i
 
        # find prime factors
        for j in range(2,ceil(sqrt(num)) + 1):
            if (num % j == 0):
                 
                # store if prime factor
                v[i].append(j)
 
                while (num % j == 0):
                    num = num // j
 
        if(num > 2):
            v[i].append(num)
 
# Function that returns answer
# for every query
def query(number, n):
    return v[number][n - 1]
 
# Driver Code
 
# Function to pre-store unique prime factors
preprocess()
 
# 1st query
number = 6
n = 1
print(query(number, n))
 
# 2nd query
number = 210
n = 3
print(query(number, n))
 
# 3rd query
number = 210
n = 2
print(query(number, n))
 
# 4th query
number = 60
n = 2
print(query(number, n))
 
# This code is contributed by mohit kumar 29

C#

// C# program to answer queries
// for N-th prime factor of a number
using System;
using System.Collections.Generic;
 
class GFG
{
     
static int N = 100001;
 
// 2-D vector that stores prime factors
static List<int> []v = new List<int>[N];
 
// Function to pre-store prime
// factors of all numbers till 10^6
static void preprocess()
{
    // calculate unique prime factors for
    // every number till 10^6
    for (int i = 1; i < N; i++)
    {
 
        int num = i;
 
        // find prime factors
        for (int j = 2; j <= Math.Sqrt(num); j++)
        {
            if (num % j == 0)
            {
 
                // store if prime factor
                v[i].Add(j);
 
                while (num % j == 0)
                {
                    num = num / j;
                }
            }
        }
        if(num > 2)
        v[i].Add(num);
    }
}
 
// Function that returns answer
// for every query
static int query(int number, int n)
{
    return v[number][n - 1];
}
 
// Driver Code
public static void Main(String[] args)
{
 
    for (int i = 0; i < N; i++)
        v[i] = new List<int>();
 
    // Function to pre-store unique prime factors
    preprocess();
 
    // 1st query
    int number = 6, n = 1;
    Console.Write(query(number, n) +"\n");
 
    // 2nd query
    number = 210; n = 3;
    Console.Write(query(number, n) +"\n");
 
    // 3rd query
    number = 210; n = 2;
    Console.Write(query(number, n) +"\n");
 
    // 4th query
    number = 60; n = 2;
    Console.Write(query(number, n) +"\n");
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript program to answer queries
// for N-th prime factor of a number
const N = 1000001;
 
// 2-D vector that stores prime factors
let v = new Array();
 
for (let i = 0; i < N; i++) {
    v.push(new Array())
}
// Function to pre-store prime
// factors of all numbers till 10^6
function preprocess()
{
 
    // calculate unique prime factors for
    // every number till 10^6
    for (let i = 1; i < N; i++) {
 
        let num = i;
 
        // find prime factors
        for (let j = 2; j <= Math.sqrt(num); j++) {
            if (num % j == 0) {
 
                // store if prime factor
                v[i].push(j);
 
                while (num % j == 0) {
                    num = num / j;
                }
            }
        }
 
        if (num > 2)
            v[i].push(num);
 
    }
}
 
// Function that returns answer
// for every query
function query(number, n) {
    return v[number][n - 1];
}
 
// Driver Code
 
// Function to pre-store unique prime factors
preprocess();
 
// 1st query
let number = 6, n = 1;
document.write(query(number, n) + "<br>");
 
// 2nd query
number = 210, n = 3;
document.write(query(number, n) + "<br>");
 
// 3rd query
number = 210, n = 2;
document.write(query(number, n) + "<br>");
 
// 4th query
number = 60, n = 2;
document.write(query(number, n) + "<br>");
 
// This code is contributed gfgking
</script>
Producción: 

2
5
3
3

 

Complejidad de tiempo: O(1) por consulta y O(maxN * log(maxN)) para preprocesamiento, donde maxN = 10 6 .
Espacio auxiliar: O(N * 8) en el peor de los casos
 

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *