Find Multiples of 2 or 3 or 5 less than or equal to N | Bit count function ; 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
< ? php function popcount ( $ value ) { $ count = 0 ; while ( $ value ) { $ count += ( $ value & 1 ) ; $ value = $ value >> 1 ; } return $ count ; } function countMultiples ( $ n ) { $ multiple = array ( 2 , 3 , 5 ) ; $ count = 0 ; $ mask = pow ( 2 , 3 ) ; for ( $ i = 1 ; $ i < $ mask ; $ i ++ ) { $ prod = 1 ; for ( $ j = 0 ; $ j < 3 ; $ j ++ ) { if ( $ i & 1 << $ j ) $ prod = $ prod * $ multiple [ $ j ] ; } if ( popcount ( $ i ) % 2 == 1 ) $ count = $ count + ( int ) ( $ n / $ prod ) ; else $ count = $ count - ( int ) ( $ n / $ prod ) ; } return $ count ; } $ n = 10 ; echo countMultiples ( $ n ) ; ? >