C++에서 N보다 작거나 같은 2 또는 3 또는 5의 배수 찾기

이 문제에서 숫자 N이 주어집니다. 우리의 임무는 N보다 작거나 같은 2, 3 또는 5의 배수를 찾는 것입니다.

문제 설명 − 2, 3 또는 5로 나눌 수 있는 1부터 N까지의 모든 요소를 ​​계산합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

N = 7

출력

5

설명

All the elements from 1 to 7 are : 1, 2, 3, 4, 5, 6, 7.
Elements divisible by 2/3/5 are 2, 3, 4, 5, 6

솔루션 접근 방식

문제를 해결하는 간단한 방법은 1에서 N까지의 모든 숫자를 탐색하고 2, 3 또는 5로 나누어진 모든 숫자를 계산하는 것입니다.

알고리즘

초기화 - 개수 =0

1단계 - i =1에서 N에 대한 루프

1.1단계 :if(i%2 ==0 || i%3 ==0 || i%5 ==0), count++.

2단계 - 반환 횟수.

또 다른 접근 방식

문제를 해결하는 더 효과적인 방법은 집합 이론을 사용하는 것입니다.

2로 나누어 떨어지는 수의 개수는 n(2)

3으로 나누어 떨어지는 수의 개수는 n(3)입니다.

5로 나누어 떨어지는 수의 개수는 n(5)

2와 3으로 나누어 떨어지는 수의 개수는 n(2 n 3)

2와 5로 나누어 떨어지는 수의 개수는 n(2 n 5)입니다.

3과 5로 나누어 떨어지는 수의 개수는 n(3 n 5)입니다.

2, 3, 5로 나누어 떨어지는 수의 개수는 n(2 n 3 n 5)

2, 3, 5로 나누어 떨어지는 수의 개수는 n(2 U 3 U 5)

집합론에 기초하여

n(2 ∪ 3 ∪ 5) =n(2) + n(3) + n(5) - n(2 ∩ 3) - n(2 ∩ 5) - n(3 ∩ 5) + n(2 ∩ 3 ∩ 5)

숫자의 비트 마스크를 계산하여 솔루션을 찾습니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <bits/stdc++.h>
using namespace std;
int countMultiples(int n) {
   int values[] = { 2, 3, 5 };
   int countMultiples = 0, bitMask = pow(2, 3);
   for (int i = 1; i < bitMask; i++) {
      int prod = 1;
      for (int j = 0; j < 3; j++) {
         if (i & 1 << j)
            prod = prod * values[j];
      }
      if (__builtin_popcount(i) % 2 == 1)
         countMultiples = countMultiples + n / prod;
      else
         countMultiples = countMultiples - n / prod;
   }
   return countMultiples;
}
int main() {
   int n = 13;
   cout<<"The number of multiples till "<<n<<" is "<<countMultiples(n)<<endl;
   return 0;
}

출력

The number of multiples till 13 is 9