Count numbers in a range having GCD of powers of prime factors equal to 1 | Python3 implementation of the approach ; Vector to store powers greater than 3 ; Set to store perfect squares ; Set to store powers other than perfect squares ; Pushing squares ; if the values is already a perfect square means present in the set ; Run loop until some power of current number doesn 't exceed MAX ; Pushing only odd powers as even power of a number can always be expressed as a perfect square which is already present in set squares ; Inserting those sorted values of set into a vector ; Precompute the powers ; Calculate perfect squares in range using sqrtl function ; Calculate upper value of R in vector using binary search ; Calculate lower value of L in vector using binary search ; Calculate perfect powers ; Compute final answer ; Driver Code
from bisect import bisect as upper_bound NEW_LINE from bisect import bisect_left as lower_bound NEW_LINE from math import floor NEW_LINE N = 1000005 NEW_LINE MAX = 10 ** 18 NEW_LINE powers = [ ] NEW_LINE squares = dict ( ) NEW_LINE s = dict ( ) NEW_LINE def powersPrecomputation ( ) : NEW_LINE INDENT for i in range ( 2 , N ) : NEW_LINE INDENT squares [ i * i ] = 1 NEW_LINE if ( i not in squares . keys ( ) ) : NEW_LINE INDENT continue NEW_LINE DEDENT temp = i NEW_LINE while ( i * i <= ( MAX // temp ) ) : NEW_LINE INDENT temp *= ( i * i ) NEW_LINE s [ temp ] = 1 NEW_LINE DEDENT DEDENT for x in s : NEW_LINE INDENT powers . append ( x ) NEW_LINE DEDENT DEDENT def calculateAnswer ( L , R ) : NEW_LINE INDENT powersPrecomputation ( ) NEW_LINE perfectSquares = floor ( ( R ) ** ( .5 ) ) - floor ( ( L - 1 ) ** ( .5 ) ) NEW_LINE high = upper_bound ( powers , R ) NEW_LINE low = lower_bound ( powers , L ) NEW_LINE perfectPowers = perfectSquares + ( high - low ) NEW_LINE ans = ( R - L + 1 ) - perfectPowers NEW_LINE return ans NEW_LINE DEDENT L = 13 NEW_LINE R = 20 NEW_LINE print ( calculateAnswer ( L , R ) ) NEW_LINE