Count of numbers up to N having at least one prime factor common with N | C ++ program for the above approach ; Function to calculate the value of Euler 's totient function ; Initialize result with N ; Find all prime factors of N and subtract their multiples ; Check if p is a prime factor ; If found to be true , then update N and result ; If N has a prime factor greater than sqrt ( N ) , then there can be at - most one such prime factor ; Function to count all the numbers in the range [ 1 , N ] having common factor with N other than 1 ; Stores the resultant count ; Print the count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int phi ( int N ) { int result = N ; for ( int p = 2 ; p * p <= N ; ++ p ) { if ( N % p == 0 ) { while ( N % p == 0 ) N /= p ; result -= result / p ; } } if ( N > 1 ) result -= result / N ; return result ; } int countNumbers ( int N ) { int count = N - phi ( N ) ; cout << count ; } int main ( ) { int N = 5 ; countNumbers ( N ) ; return 0 ; }