Count numbers up to N having exactly 5 divisors | Java program for the above approach ; Function to calculate the value of ( x ^ y ) using binary exponentiation ; Stores the value of x ^ y ; Base Case ; If y is odd multiply x with result ; Otherwise , divide y by 2 ; Function to perform the Sieve Of Eratosthenes to find the prime number over the range [ 1 , 10 ^ 5 ] ; If prime [ p ] is not changed then it is a prime ; Set all the multiples of p to non - prime ; Iterate over the range [ 1 , MAX ] ; Store all the prime number ; Function to find the primes having only 5 divisors ; Base Case ; First value of the pair has the prime number and the second value has the count of primes till that prime numbers ; Precomputing all the primes ; Perform the Binary search ; Calculate the fourth power of the curr and prev ; Return value of mid ; Return value of mid - 1 ; Update the value of high ; Update the value of low ; Driver code
import java . util . Vector ; public class GFG { static int MAX = ( int ) 1e5 ; public static class pair { long first ; long second ; pair ( long first , long second ) { this . first = first ; this . second = second ; } } static long power ( long x , long y ) { long res = 1 ; if ( x == 0 ) return 0 ; while ( y > 0 ) { if ( ( y & 1 ) == 1 ) res = ( res * x ) ; y = y >> 1 ; x = ( x * x ) ; } return res ; } static void SieveOfEratosthenes ( Vector < pair > v ) { boolean prime [ ] = new boolean [ MAX + 1 ] ; for ( int i = 0 ; i < prime . length ; i ++ ) { prime [ i ] = true ; } prime [ 1 ] = false ; for ( int p = 2 ; p * p <= MAX ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * 2 ; i <= MAX ; i += p ) prime [ i ] = false ; } } int num = 1 ; for ( int i = 1 ; i <= MAX ; i ++ ) { if ( prime [ i ] ) { v . add ( new pair ( i , num ) ) ; num ++ ; } } } static long countIntegers ( long n ) { if ( n < 16 ) { return 0 ; } Vector < pair > v = new Vector < > ( ) ; SieveOfEratosthenes ( v ) ; int low = 0 ; int high = v . size ( ) - 1 ; while ( low <= high ) { int mid = ( low + high ) / 2 ; long curr = power ( v . get ( mid ) . first , 4 ) ; long prev = power ( v . get ( mid - 1 ) . first , 4 ) ; if ( curr == n ) { return v . get ( mid ) . second ; } else if ( curr > n && prev <= n ) { return v . get ( mid - 1 ) . second ; } else if ( curr > n ) { high = mid - 1 ; } else { low = mid + 1 ; } } return 0 ; } public static void main ( String [ ] args ) { long N = 100 ; System . out . println ( countIntegers ( N ) ) ; } }