N | Python3 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 ; Function to pre - store unique prime factors ; 1 st query ; 2 nd query ; 3 rd query ; 4 th query
from math import sqrt , ceil NEW_LINE N = 10001 NEW_LINE v = [ [ ] for i in range ( N ) ] NEW_LINE def preprocess ( ) : NEW_LINE INDENT for i in range ( 1 , N ) : NEW_LINE INDENT num = i NEW_LINE for j in range ( 2 , ceil ( sqrt ( num ) ) + 1 ) : NEW_LINE INDENT if ( num % j == 0 ) : NEW_LINE INDENT v [ i ] . append ( j ) NEW_LINE while ( num % j == 0 ) : NEW_LINE INDENT num = num // j NEW_LINE DEDENT DEDENT DEDENT if ( num > 2 ) : NEW_LINE INDENT v [ i ] . append ( num ) NEW_LINE DEDENT DEDENT DEDENT def query ( number , n ) : NEW_LINE INDENT return v [ number ] [ n - 1 ] NEW_LINE DEDENT preprocess ( ) NEW_LINE number = 6 NEW_LINE n = 1 NEW_LINE print ( query ( number , n ) ) NEW_LINE number = 210 NEW_LINE n = 3 NEW_LINE print ( query ( number , n ) ) NEW_LINE number = 210 NEW_LINE n = 2 NEW_LINE print ( query ( number , n ) ) NEW_LINE number = 60 NEW_LINE n = 2 NEW_LINE print ( query ( number , n ) ) NEW_LINE