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