Count numbers in a range having GCD of powers of prime factors equal to 1 | Java implementation of above idea ; 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
import java . util . * ; class GFG { static int N = 1000005 ; static long MAX = ( long ) 1e18 ; static Vector < Long > powers = new Vector < > ( ) ; static TreeSet < Long > squares = new TreeSet < > ( ) ; static TreeSet < Long > s = new TreeSet < > ( ) ; static void powersPrecomputation ( ) { for ( long i = 2 ; i < N ; i ++ ) { squares . add ( i * i ) ; if ( squares . contains ( i ) ) continue ; long temp = i ; while ( i * i <= MAX / temp ) { temp *= ( i * i ) ; s . add ( temp ) ; } } for ( long x : s ) powers . add ( x ) ; } static long calculateAnswer ( long L , long R ) { powersPrecomputation ( ) ; long perfectSquares = ( long ) ( Math . floor ( Math . sqrt ( R ) ) - Math . floor ( Math . sqrt ( L - 1 ) ) ) ; long high = Collections . binarySearch ( powers , R ) ; long low = Collections . binarySearch ( powers , L ) ; long perfectPowers = perfectSquares + ( high - low ) ; long ans = ( R - L + 1 ) - perfectPowers ; return ans ; } public static void main ( String [ ] args ) { long L = 13 , R = 20 ; System . out . println ( calculateAnswer ( L , R ) ) ; } }