Given Q queries which consist of two integers, one is number(1 <= number <= 106) and the other is N., the task is to find the N-th prime factor of the given number.
Examples:
Input: Number of Queries, Q = 4
number = 6, N = 1
number = 210, N = 3
number = 210, N = 2
number = 60, N = 2
Output:
2
5
3
2Explanations:
- For number = 6, The prime factors 2 and 3. So, 2 is the 1st one.
- For number = 210, The prime factors 2, 3, 5 and 7. So, 5 is the 3rd one.
- For number = 210, The prime factors 2, 3, 5 and 7. So, 3 is the 2nd one.
- For number = 60, The prime factors 2, 2, 3 and 5. So, 2 is the 2nd one.
A naive approach is to factorize every number and store the prime factors. Print the N-th prime factors thus stored.
Time Complexity: O(log(n)) per query.
An efficient approach is to pre-calculate all the prime factors of the number and store the numbers in a sorted order in a 2-D vector. Since the number will not be more than 106, the number of unique prime factors will be around 7-8 at max(because of 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 >= 106). Once the numbers are stored, the query can be answered in O(1) as the n-1th index will have the answer in numberth row.
Below is the implementation of the above approach:
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 factorsvector<int> v[N];// Function to pre-store prime// factors of all numbers till 10^6void 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 queryint query(int number, int n){ return v[number][n - 1];}// Driver Codeint 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 numberimport java.util.*;class GFG{ static int N = 1000001;// 2-D vector that stores prime factorsstatic Vector<Integer> []v = new Vector[N];// Function to pre-store prime// factors of all numbers till 10^6static 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 querystatic int query(int number, int n){ return v[number].get(n - 1);}// Driver Codepublic 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 numberfrom math import sqrt,ceilN = 10001# 2-D vector that stores prime factorsv = [[] for i in range(N)]# Function to pre-store prime# factors of all numbers till 10^6def 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 querydef query(number, n): return v[number][n - 1]# Driver Code# Function to pre-store unique prime factorspreprocess()# 1st querynumber = 6n = 1print(query(number, n))# 2nd querynumber = 210n = 3print(query(number, n))# 3rd querynumber = 210n = 2print(query(number, n))# 4th querynumber = 60n = 2print(query(number, n))# This code is contributed by mohit kumar 29 |
C#
// C# program to answer queries// for N-th prime factor of a numberusing System;using System.Collections.Generic;class GFG{ static int N = 100001;// 2-D vector that stores prime factorsstatic List<int> []v = new List<int>[N];// Function to pre-store prime// factors of all numbers till 10^6static 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 querystatic int query(int number, int n){ return v[number][n - 1];}// Driver Codepublic 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 numberconst N = 1000001;// 2-D vector that stores prime factorslet 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^6function 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 queryfunction query(number, n) { return v[number][n - 1];}// Driver Code// Function to pre-store unique prime factorspreprocess();// 1st querylet number = 6, n = 1;document.write(query(number, n) + "<br>");// 2nd querynumber = 210, n = 3;document.write(query(number, n) + "<br>");// 3rd querynumber = 210, n = 2;document.write(query(number, n) + "<br>");// 4th querynumber = 60, n = 2;document.write(query(number, n) + "<br>");// This code is contributed gfgking</script> |
Output
2 5 3 3
Time Complexity: O(1) per query and O(maxN * log(maxN)) for pre-processing, where maxN = 106.
Auxiliary Space: O(N * 8) in worst case
Another Efficient Approach:
Another efficient approach is to use Sieve of Eratosthenes. Note that this solution is efficient when we need k-th prime factor for multiple test cases.
Approach:
The approach is to do preprocessing and store least prime factor of all numbers in given range. Once we have least prime factors stored in an array, we can find k-th prime factor by repeatedly dividing n with least prime factor while it is divisible, then repeating the process for reduced n.
Steps:
- The program starts by defining a function called “isPrime” that checks if a given number is prime or not. It returns a boolean value true if the number is prime and false otherwise.
- The program then defines a function called “AllPrimeFactors” that takes an integer argument N and returns a vector of all possible prime factors of the number. It uses a loop to iterate through all numbers from 2 to the square root of N and checks if each number is a factor of N. If it is, it adds the number to the vector and divides N by that number. It continues this process until N is no longer divisible by the current factor. If the remaining N is also a prime number, it adds it to the vector.
- The program defines a function called “query” that takes two integer arguments – a number and an integer k. It first calls the “AllPrimeFactors” function to get all possible prime factors of the number. It then checks if the number itself is a prime number and if the value of k is 1. If both conditions are true, it returns the number as the answer to the query. If the size of the vector of prime factors is less than k, it returns -1. Otherwise, it returns the k-th element of the vector as the answer to the query.
- The program then defines the “main” function which is the entry point of the program. It creates four queries by setting different values of “number” and “n”. It calls the “query” function for each query and prints the result to the console.
- Finally, the program ends by returning 0 from the main function.
C++
// C++ program to answer queries// for N-th prime factor of a number// Using Sieve of Eratosthenes method#include <bits/stdc++.h>using namespace std;// Check if the number if prime or notbool isPrime(int n){ if (n <= 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true;}// Function to find all the possible prime factorsvector<int> AllPrimeFactors(int N){ vector<int> v; for (int i = 2; i * i <= N; i++) { while (N % i == 0) { v.push_back(i); N = N / i; if (isPrime(N)) { v.push_back(N); N = N / N; } } } return v;}// Function that returns answer// for every queryint query(int n, int k){ vector<int> ans = AllPrimeFactors(n); if (isPrime(n) && k == 1) { return n; } if (ans.size() < k) { return -1; } return ans[k - 1];}// Driver Codeint main(){ // 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;}// This code is contributed by Susobhan Akhuli |
Java
// Java program to answer queries// for N-th prime factor of a number// Using Sieve of Eratosthenes methodimport java.util.Vector;public class GFG { // Check if the number if prime or not public static boolean isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } // Function to find all the possible prime factors public static Vector<Integer> AllPrimeFactors(int N) { Vector<Integer> v = new Vector<Integer>(); for (int i = 2; i * i <= N; i++) { while (N % i == 0) { v.add(i); N = N / i; if (isPrime(N)) { v.add(N); N = N / N; } } } return v; } // Function that returns answer // for every query public static int query(int n, int k) { Vector<Integer> ans = AllPrimeFactors(n); if (isPrime(n) && k == 1) { return n; } if (ans.size() < k) { return -1; } return ans.get(k - 1); } // Driver Code public static void main(String[] args) { // 1st query int number = 6, n = 1; System.out.println(query(number, n)); // 2nd query number = 210; n = 3; System.out.println(query(number, n)); // 3rd query number = 210; n = 2; System.out.println(query(number, n)); // 4th query number = 60; n = 2; System.out.println(query(number, n)); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python program to answer queries# for N-th prime factor of a number# Using Sieve of Eratosthenes methodimport math# Check if the number is prime or notdef isPrime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n))+1): if n % i == 0: return False return True# Function to find all the possible prime factorsdef AllPrimeFactors(N): v = [] i = 2 while i * i <= N: while N % i == 0: v.append(i) N = N // i if isPrime(N): v.append(N) N = N // N i += 1 if N > 1: v.append(N) return v# Function that returns answer for every querydef query(n, k): ans = AllPrimeFactors(n) if isPrime(n) and k == 1: return n if len(ans) < k: return -1 return ans[k-1]# Driver Codeif __name__ == '__main__': # 1st query number, n = 6, 1 print(query(number, n)) # 2nd query number, n = 210, 3 print(query(number, n)) # 3rd query number, n = 210, 2 print(query(number, n)) # 4th query number, n = 60, 2 print(query(number, n))# This code is contributed by Susobhan Akhuli |
C#
// C# program to answer queries// for N-th prime factor of a number// Using Sieve of Eratosthenes methodusing System;using System.Collections.Generic;class Program { // Check if the number if prime or not static bool IsPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } // Function to find all the possible prime factors static List<int> AllPrimeFactors(int N) { List<int> v = new List<int>(); for (int i = 2; i * i <= N; i++) { while (N % i == 0) { v.Add(i); N = N / i; if (IsPrime(N)) { v.Add(N); N = N / N; } } } return v; } // Function that returns answer // for every query static int Query(int n, int k) { List<int> ans = AllPrimeFactors(n); if (IsPrime(n) && k == 1) { return n; } if (ans.Count < k) { return -1; } return ans[k - 1]; } // Driver Code static void Main(string[] args) { // 1st query int number = 6, n = 1; Console.WriteLine(Query(number, n)); // 2nd query number = 210; n = 3; Console.WriteLine(Query(number, n)); // 3rd query number = 210; n = 2; Console.WriteLine(Query(number, n)); // 4th query number = 60; n = 2; Console.WriteLine(Query(number, n)); }}// This code is contributed by Susobhan Akhuli |
Javascript
function isPrime(n) { if (n <= 1) { return false; } for (let i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true;}function allPrimeFactors(N) { let v = []; for (let i = 2; i * i <= N; i++) { while (N % i == 0) { v.push(i); N = N / i; if (isPrime(N)) { v.push(N); N = N / N; } } } return v;}function query(n, k) { let ans = allPrimeFactors(n); if (isPrime(n) && k == 1) { return n; } if (ans.length < k) { return -1; } return ans[k - 1];}// Test caseslet number = 6, n = 1;console.log(query(number, n));number = 210, n = 3;console.log(query(number, n));number = 210, n = 2;console.log(query(number, n));number = 60, n = 2;console.log(query(number, n)); |
Output
2 5 3 2
Time Complexity: O(N*log(log(N))), where N is the number.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
