Count of numbers up to N having at least one prime factor common with N | Python 3 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
import math NEW_LINE def countNumbers ( N ) : NEW_LINE INDENT count = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( math . gcd ( i , N ) != 1 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT print ( count ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 5 NEW_LINE countNumbers ( N ) NEW_LINE DEDENT