Xóa bài viết
Bạn có chắc chắn muốn xóa bài viết này không ?
Xóa bình luận
Bạn có chắc chắn muốn xóa bình luận này không ?
#1 Số Lượng Số Từ 1 -> n Không Chia Hết Cho Bất Kỳ Số Nào Từ 2 -> 10
Số Lượng Số Từ 1 -> n Không Chia Hết Cho Bất Kỳ Số Nào Từ 2 -> 10
Liên Hệ
- Sàng Nguyên Tố
- Tổ hợp các số tạo ra từ tích của các thừa số nguyên tố p1, p2, p3, ... , pk
- Số lượng các số (chia hết / không chia hêt) cho bất kì các số nguyên tố p1, p2, p3, ... , pk
- Dạng Tổng Quát: Số Lượng Số Từ a -> b Không Chia Hết Cho Bất Kỳ Số Nào Từ c -> d
Ý Tưởng
- Các số từ 1 -> n không có thừa số nguyên tố từ 2 -> 10
- Số nguyên tố từ 2 đến 10 ( Sàng Nguyên Tố )
Giải Quyết Vấn Đề
Cách 1 ( Chọn Trực Tiếp ):
// Time : O(n)
// Space: O(1)
int res = 0;
for (int i=1; i<=n; i++){
/// Số Nguyên Tố từ 2->10 : 2, 3, 5, 7
if ( i%2 != 0 && i%3 != 0 && i%5 != 0 && i%7 != 0){
res++;
}
}
cout << res;
Ưu Điểm
- Dễ cài đặt
- Ý tưởng đơn giản
Khuyết Điểm
- Độ phức tạp cao
Cách 2 ( Tính Phần Bù ):
-Tìm số lượng không chia hết cho các thừa số nguyên tố (2->10) có thể khó tìm công thức. Nhưng tìm các số chia hết cho các thừa số nguyên tố (2->10) lại khá dễ
-Áp dụng tính chất của các tập hợp:
A ∪ B ∪ C = (A + B + C) - (A∩B + A∩C + B∩C) + (A∩B∩C)
và Dạng Tổng Quát
// Time: O(1)
// Space: O(1)
int d2 = n/2; // 2
int d3 = n/3; // 3
int d5 = n/5; // 5
int d7 = n/7; // 7
int d6 = n/6; // 2, 3
int d10 = n/10; // 2, 5
int d14 = n/14; // 2, 7
int d15 = n/15; // 3, 5
int d21 = n/21; // 3, 7
int d35 = n/35; // 5, 7
int d30 = n/30; // 2, 3, 5
int d42 = n/42; // 2, 3, 7
int d70 = n/70; // 2, 5, 7
int d105 = n/105; // 3, 5, 7
int d210 = n/210; // 2, 3, 5, 6
int d2_3_5_7 = (d2 + d3 + d5 + d7) - (d6 + d10 + d14 + d15 + d21 + d35) + (d30 + d42 + d70 + d105) - d210;
ull res = n - d2_3_5_7;
cout << res;
Ưu Điểm
- Độ phức tạp tốt ( Chỉ tính số lượng chứ không liệt kê rồi đếm nên Cách 1, Tính chất số học)
Khuyết Điểm
- Tìm tổ hợp các thừa số nguyên tố ( Số lượng tổ hợp: 2^k - 1 | k: số thừa số nguyên tố
Ghi Chú
Số lượng các số từ a -> b (chia hết / không chia hêt) cho bất kì các số nguyên tố p1, p2, p3, ... , pk
Bình luận

{{ comment.user.name }}
Bỏ hay
Hay

Bài viết liên quan

0
0
Số Lượng Số Từ a b Không Chia Hết Cho Bất Kỳ Số Nào Từ c d Liên Hệ Sàng Nguyên Tố (Link) Ý Tưởng Tiếp nối của cách 2 (1) Giải Quyết Vấn Đề...