#1 Số Lượng Số Từ 1 -> n Không Chia Hết Cho Bất Kỳ Số Nào Từ 2 -> 10
#giaithuat #sohoc
2
Male avatar

DatLuu viết ngày 25/06/2019

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ệ

Ý 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)
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


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

Male avatar

DatLuu

2 bài viết.
0 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Bài viết liên quan
Male avatar
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 Đề...
DatLuu viết 2 tháng trước
0 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


Male avatar
{{userFollowed ? 'Following' : 'Follow'}}
2 bài viết.
0 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!