Sum of all numbers up to N that are co | C ++ program for the above approach ; Function to return gcd of a and b ; Base Case ; Recursive GCD ; Function to calculate the sum of all numbers till N that are coprime with N ; Stores the resultant sum ; Iterate over [ 1 , N ] ; If gcd is 1 ; Update sum ; Return the final sum ; Driver Code ; Given N ; Function Call
#include <iostream> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } int findSum ( unsigned int N ) { unsigned int sum = 0 ; for ( int i = 1 ; i < N ; i ++ ) { if ( gcd ( i , N ) == 1 ) { sum += i ; } } return sum ; } int main ( ) { int N = 5 ; cout << findSum ( N ) ; return 0 ; }