이 기사에서는 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에서 num까지의 모든 숫자를 확인하면 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.
어디,
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)] )
예시
#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;
} 출력
The count of numbers, not div by [2, 10] is: 5
결론
이 기사에서는 2에서 n까지 나누어지지 않는 수를 찾는 방법에 대해 논의했습니다. 이 문제를 해결하기 위해 우리는 포함-배제 원칙에 대해 논의했습니다. 우리는 또한 O(1) 복잡성으로 결과를 얻기 위해 접근 방식을 적용하는 C++ 프로그램에 대해 논의했습니다. 이 프로그램은 Java, C, Python 등과 같은 다른 언어로 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.