CountOfNumbersDivisibleByPrimeLessThanTwenty.java

long countOfNumbers(long N, int[]primeArray) {
 
 
      long sum=0;
  
      int totalNumberOfSubsets = 1<<primeArray.length;
      // loop to generate all subsets from prime array
      for(int i=1;i<totalNumberOfSubsets;i++) {          
        
        long count=1;
          
        for(int k=0;k<primes.length;k++){
              //bit is set then get lcm
              if((i&(1<<k))!=0) {
                  count = lcm(count, primes[k]);
              }                    
          }
          
          // if bit is set i.e number i has odd number of terms, add to total sum 
          // this is because from the inclusion exclusion principle we add odd terms and subtract even
          if ((1 & Long.bitCount(i))>0) {
            sum += N/count;
          } else {
            // this else part indicates even terms so substract from total sum
            sum-=N/count;
         }
        
      }
  return sum;
}

private long lcm(long a, long b) {
  return (a/gcd(a,b))*b;
}

private long gcd(long a, long b) {
  if(a==0) {
    return b;
  }
  return gcd(b%a,a);
}
            
             
     
        
}