Product of all numbers up to N that are co | Function to return gcd of a and b ; Base Case ; Recursive GCD ; Function to find the product of all the numbers till N that are relatively prime to N ; Stores the resultant product ; Iterate over [ 2 , N ] ; If gcd is 1 , then find the product with result ; Return the final product ; Driver Code
def gcd ( a , b ) : NEW_LINE INDENT if ( a == 0 ) : NEW_LINE INDENT return b ; NEW_LINE DEDENT return gcd ( b % a , a ) ; NEW_LINE DEDENT def findProduct ( N ) : NEW_LINE INDENT result = 1 ; NEW_LINE for i in range ( 2 , N ) : NEW_LINE INDENT if ( gcd ( i , N ) == 1 ) : NEW_LINE INDENT result *= i ; NEW_LINE DEDENT DEDENT return result ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 ; NEW_LINE print ( findProduct ( N ) ) ; NEW_LINE DEDENT