Find Nth smallest number having exactly 4 divisors | Function to find the nth number which has exactly 4 divisors ; The divs [ ] array to store number of divisors of every element ; The vis [ ] array to check if given number is considered or not ; The cnt stores number of elements having exactly 4 divisors ; Iterate while cnt less than n ; If i is a prime ; Iterate in the range [ 2 * i , 1000000 ] with increment of i ; If the number j is already considered ; Dividing currNum by i until currNum % i is equal to 0 ; Case a single prime in its factorization ; Case of two distinct primes which divides j exactly once each ; Given Input ; Function Call
def nthNumber ( n ) : NEW_LINE INDENT divs = [ 0 for i in range ( 1000000 ) ] ; NEW_LINE vis = [ 0 for i in range ( 1000000 ) ] ; NEW_LINE cnt = 0 ; NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT if ( divs [ i ] == 0 ) : NEW_LINE INDENT for j in range ( 2 * i , 1000000 ) : NEW_LINE INDENT if ( vis [ j ] ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT vis [ j ] = 1 ; NEW_LINE currNum = j ; NEW_LINE count = 0 ; NEW_LINE while ( currNum % i == 0 ) : NEW_LINE INDENT divs [ j ] += 1 ; NEW_LINE currNum = currNum // i ; NEW_LINE count += 1 ; NEW_LINE DEDENT if ( currNum == 1 and count == 3 and divs [ j ] == 3 ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT elif ( currNum != 1 and divs [ currNum ] == 0 and count == 1 and divs [ j ] == 1 ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT if ( cnt == n ) : NEW_LINE INDENT return j ; NEW_LINE DEDENT DEDENT DEDENT DEDENT return - 1 ; NEW_LINE DEDENT N = 24 ; NEW_LINE print ( nthNumber ( N ) ) ; NEW_LINE