Count of numbers up to N having at least one prime factor common with N | C ++ program for the above approach ; Function to count all the numbers in the range [ 1 , N ] having common factor with N other than 1 ; Stores the count of numbers having more than 1 factor with N ; Iterate over the range [ 1 , N ] ; If gcd is not 1 then increment the count ; Print the resultant count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countNumbers ( int N ) { int count = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( __gcd ( i , N ) != 1 ) count ++ ; } cout << count ; } int main ( ) { int N = 5 ; countNumbers ( N ) ; return 0 ; }