C++를 사용하여 범위 내 어떤 숫자로도 나누어지지 않는 숫자 찾기

이 글에서는 2와 10 사이의 어떤 숫자로도 나누어지지 않는 1과 n(주어진) 사이의 숫자를 찾는 문제에 대해 논의할 것입니다. 몇 가지 예를 들어 이해해 봅시다. -

Input : num = 14
Output : 3
Explanation: There are three numbers, 1, 11, and 13, which are not divisible.

Input : num = 21
Output : 5
Explanation: There are five numbers 1, 11, 13, 17, and 19, which are not divisible.

해결 방법

간단한 방법

1부터 숫자까지 모든 숫자를 검사하면 2에서 10 사이의 어떤 숫자로 나눌 수 있는지 여부를 확인합니다. 그렇지 않은 경우 개수를 늘리십시오. 하지만 이 방법은 시간이 너무 많이 걸리므로 시간 복잡도가 증가합니다.

효율적인 방법

우리가 생각할 수 있는 가장 좋은 방법은 먼저 1부터 num까지의 숫자([2, 10] 범위의 임의의 숫자일 수 있음)를 찾은 다음 이 숫자를 num에서 빼는 것입니다.

먼저 2, 3, 4, 5,10으로 나누어지는 숫자를 모두 찾아야 합니다. 그러나 4, 6, 8, 10으로 나누어지는 수는 2로 나누어지고, 3으로 나누어지는 수는 6과 9로 나누어집니다.

2, 3, 5로 나누어지는 숫자를 모두 찾아야 합니다. , 그리고 7. 포함-배제 원칙에 따라 계산할 수 있습니다.

포함-배제 원칙

각 개별 세트의 크기를 포함해야 하고, 쌍별 교차점의 크기를 제거하고, 세 세트의 모든 교차점의 크기를 추가해야 한다는 등의 내용이 있습니다.

모든 숫자를 찾는 공식은

= NUM – X + Y – Z + A.

where,

X = num divisible by 2, 3, 5, 7 ( [num / 2] + [num / 3] + [num / 5] + [num / 7] )

Y = num divisible by (2,3), (2, 5), (2, 7), (3, 5), (3, 5), (3, 7) and (5, 7) = ( [num / (2 * 3)] + [num / (2 * 5)] + [num / (2 * 7)] + [num / (3 * 5)] + num / (3 * 7)] + [num / (5 * 7)] ).

Z = num divisible by (2, 3, 5), (2, 3, 7), (2, 5, 7) and (3, 5, 7) = ( [num / (2 * 3 * 5)] + [num / (2 * 3 * 7)] + [num / (2 * 5 * 7)] + [num / (3 * 5 * 7)] )

A = num divisible by (2, 3, 5, 7) = ( [num / (2 * 3 * 5 * 7)] )

Example

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 21, result;
   // applying formula from inclusion - exclusion principle
   // to find the count of numbers not divisible by any number from 2 to 10.
   result = n - n / 2 - n / 3 - n / 5 - n / 7
      + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35
      - n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
   cout << "The count of numbers, not div by [2, 10] is: " << result;

   return 0;
}

Output

The count of numbers, not div by [2, 10] is: 5

결론

이 글에서는 2와 n 사이에서 나누어지지 않는 숫자를 찾는 방법에 대해 논의했습니다. 이 문제를 해결하기 위해 포함-배제 원칙을 논의합니다. 또한 이 방법을 적용하여 O(1) 복잡도의 결과를 얻는 C++ 프로그램에 대해서도 논의합니다. 이 프로그램은 Java, C, Python 등과 같은 다른 언어로 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 C++를 사용하여 범위 내 어떤 숫자로도 나누어지지 않는 숫자 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!