Count of integers up to N which are non divisors and non coprime with N | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int count ( int n ) { int phi [ n + 1 ] = { 0 } ; int divs [ n + 1 ] = { 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 ) ; } int main ( ) { int N = 42 ; cout << count ( N ) ; return 0 ; }