Trong bài này, chúng ta sẽ thảo luận về vấn đề tìm các số từ 1 đến n (đã cho) mà không thể chia hết cho bất kỳ số nào từ 2 đến 10. Hãy cùng tìm hiểu điều này với một số ví dụ -
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.
Phương pháp tiếp cận để tìm ra giải pháp
Cách tiếp cận đơn giản
Nếu chúng ta kiểm tra mọi số từ 1 đến num, liệu nó có thể chia cho bất kỳ số nào từ 2 đến 10. Nếu không, hãy tăng số đếm. Nhưng cách tiếp cận này sẽ mất quá nhiều thời gian do đó làm tăng độ phức tạp về thời gian.
Phương pháp tiếp cận hiệu quả
Cách tốt nhất mà chúng ta có thể nghĩ đến là trước tiên tìm các số từ 1 đến num, chia hết cho bất kỳ số nào trong phạm vi [2, 10], sau đó trừ số này với num.
Vì vậy, trước tiên, chúng ta cần tìm tất cả các số chia hết cho 2, 3, 4, 5,10. Nhưng các số chia hết cho 4, 6, 8 và 10 thì chia hết cho 2 và các số chia hết cho ba thì chia hết cho 6 và 9.
Chúng ta cần tìm tất cả các số chia hết cho 2, 3, 5 và 7. Và điều này chúng ta có thể tính toán từ nguyên tắc bao gồm - loại trừ.
Nguyên tắc loại trừ bao gồm
Nó nói rằng chúng ta nên bao gồm mọi kích thước của từng tập hợp, bạn nên loại bỏ kích thước của giao lộ theo cặp, tất cả kích thước của ba tập hợp giao nhau sẽ được thêm vào, v.v.
Công thức để tìm tất cả các số là,
= NUM – X + Y – Z + A.
Ở đâu,
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)] )
Ví dụ
#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;
} Đầu ra
The count of numbers, not div by [2, 10] is: 5
Kết luận
Trong bài này, chúng ta đã thảo luận về cách tìm các số không chia hết từ 2 đến n. Để giải quyết vấn đề này, chúng tôi đã thảo luận về nguyên tắc bao gồm - loại trừ. Chúng tôi cũng đã thảo luận về chương trình C ++ để áp dụng phương pháp thu được kết quả với độ phức tạp O (1). Bạn có thể viết chương trình này bằng bất kỳ ngôn ngữ nào khác như Java, C, Python, v.v. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.