Find Multiples of 2 or 3 or 5 less than or equal to N | Function to count number of multiples of 2 or 3 or 5 less than or equal to N ; As we have to check divisibility by three numbers , So we can implement bit masking ; we check whether jth bit is set or not , if jth bit is set , simply multiply to prod ; check for set bit ; check multiple of product ; Driver code
def countMultiples ( n ) : NEW_LINE INDENT multiple = [ 2 , 3 , 5 ] NEW_LINE count = 0 NEW_LINE mask = int ( pow ( 2 , 3 ) ) NEW_LINE for i in range ( 1 , mask ) : NEW_LINE INDENT prod = 1 NEW_LINE for j in range ( 3 ) : NEW_LINE INDENT if ( i & ( 1 << j ) ) : NEW_LINE INDENT prod = prod * multiple [ j ] NEW_LINE DEDENT DEDENT if ( bin ( i ) . count ( '1' ) % 2 == 1 ) : NEW_LINE INDENT count = count + n // prod NEW_LINE DEDENT else : NEW_LINE INDENT count = count - n // prod NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 10 NEW_LINE print ( countMultiples ( n ) ) NEW_LINE DEDENT