Count of integers up to N which are non divisors and non coprime with N | Java program to implement the above approach ; Function to return the count of integers less than N satisfying given conditions ; Stores Euler counts ; Store Divisor counts ; Based on Sieve of Eratosthenes ; Update phi values of all multiples of i ; Update count of divisors ; Return the final count ; Driver Code
import java . util . Arrays ; class GFG { public static int count ( int n ) { int [ ] phi = new int [ n + 1 ] ; Arrays . fill ( phi , 0 ) ; int [ ] divs = new int [ n + 1 ] ; Arrays . fill ( divs , 0 ) ; for ( int i = 1 ; i <= n ; i ++ ) { phi [ i ] += i ; for ( int j = i * 2 ; j <= n ; j += i ) phi [ j ] -= phi [ i ] ; for ( int j = i ; j <= n ; j += i ) divs [ j ] ++ ; } return ( n - phi [ n ] - divs [ n ] + 1 ) ; } public static void main ( String [ ] args ) { int N = 42 ; System . out . println ( count ( N ) ) ; } }