Count integers up to N that are equal to at least 2 nd power of any integer exceeding 1 | Python 3 program for the above approach ; Function to count the integers up to N that can be represented as a ^ b , where a & b > 1 ; Initialize a HashSet ; Iterating over the range [ 2 , sqrt ( N ) ] ; Generate all possible power of x ; Multiply x by i ; If the generated number lies in the range [ 1 , N ] then insert it in HashSet ; Print the total count ; Driver code
from math import sqrt NEW_LINE def printNumberOfPairs ( N ) : NEW_LINE INDENT st = set ( ) NEW_LINE for i in range ( 2 , int ( sqrt ( N ) ) + 1 , 1 ) : NEW_LINE INDENT x = i NEW_LINE while ( x <= N ) : NEW_LINE INDENT x *= i NEW_LINE if ( x <= N ) : NEW_LINE INDENT st . add ( x ) NEW_LINE DEDENT DEDENT DEDENT print ( len ( st ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 10000 NEW_LINE printNumberOfPairs ( N ) NEW_LINE DEDENT