Mẹo Hướng dẫn Viết chương trình xuất ra tất cả những số nguyên tố nhỏ hơn n theo thuật toán sàng eratosthène. Chi Tiết
Bùi Thị Kim Oanh đang tìm kiếm từ khóa Viết chương trình xuất ra tất cả những số nguyên tố nhỏ hơn n theo thuật toán sàng eratosthène. được Cập Nhật vào lúc : 2022-08-01 06:22:02 . Với phương châm chia sẻ Bí kíp Hướng dẫn trong nội dung bài viết một cách Chi Tiết 2022. Nếu sau khi đọc Post vẫn ko hiểu thì hoàn toàn có thể lại phản hồi ở cuối bài để Tác giả lý giải và hướng dẫn lại nha.
Số nguyên tố là số nguyên dương to hơn 111 và chỉ có đúng hai ước là 111 và chính nó.
Nội dung chính- 2. Kiểm tra tính nguyên tố của một số2.1. Giải thuật cơ sở2.2. Cải tiến:II. Sàng lọc số nguyên tố Eratosthenes2. Cài đặt giải thuật3. Sàng số nguyên tố trên đoạnIII. Phân tích thừa số nguyên tố1. Giải thuật cơ sở2. Cải tiến lần 13. Phân tích thừa số nguyên tố bằng sàng Eratosthenes:4. Đếm số ước của một số trong những nguyên5. Tính tổng những ước số nguyên dương của một số trong những nguyên dươngTài liệu tham khảo:
Hợp số, là những số nguyên dương to hơn 111 và có nhiều hơn nữa hai ước.
Lấy ví dụ: 555 là một số trong những nguyên tố, vì nó chỉ có đúng hai ước là 111 và 555. trái lại 101010 là một hợp số vì nó có bốn ước là một trong,2,51, 2, 51,2,5 và 101010. Số nguyên tố và những vấn đề xoay quanh nó vẫn là một chủ đề được yêu thích trong Toán học nói chung và lập trình thi đấu nói riêng.
2. Kiểm tra tính nguyên tố của một số trong những
2.1. Giải thuật cơ sở
Ý tưởng ban đầu rất đơn giản: Ta duyệt qua tất cả những số nguyên từ 222 tới N−1,N - 1,N−1, nếu như có số nào là ước của NNN thì kết luận NNN không phải số nguyên tố. Giải thuật có độ phức tạp O(N)O(N)O(N).
bool is_prime(int N) if (N < 2) return false; for (int i = 2; i < N; ++i) if (N % i == 0) return false; return true;2.2. Cải tiến:
Xuất phát từ nhận xét sau: Giả sử số nguyên dương NNN có ước là DDD (0 Sàng Eratosthenes là một giải thuật cổ xưa do nhà Toán học người Hy Lạp Eratosthenes phát minh ra để tìm những số nguyên tố nhỏ hơn 100100100. Tương truyền, khi tìm ra thuật toán, ông đã lấy lá cọ và ghi tất cả những số từ 222 cho tới 100100100 lên đó, sau đó chọc thủng những hợp số và không thay đổi những số nguyên tố. Bảng số nguyên tố còn sót lại trông rất giống một chiếc sàng. Do đó, nó mang tên là sàng Eratosthenes. Với sự phát triển của máy tính, sàng Eratosthenes trở thành một công cụ rất hữu dụng để tìm ra những số nguyên tố trong một khoảng chừng nhất định, với điều kiện bộ nhớ hoàn toàn có thể tàng trữ được. Nguyên lý hoạt động và sinh hoạt giải trí của sàng Eratosthenes như sau: Xét những số nguyên tố từ 222 tới N,sqrtN,N, với mỗi số nguyên tố ta sẽ đánh dấu những bội của nó mà to hơn nó đều là hợp số. Sau khi duyệt xong, tất cả những số không được đánh dấu sẽ là số nguyên tố. Dưới đây setup sàng lọc những số nguyên tố từ 111 tới NNN. Bạn đọc hoàn toàn có thể thắc mắc tại sao những bội của iii lại không bắt nguồn từ 2.i2.i2.i. Lí do là vì, vòng lặp duyệt những số nguyên tố tăng dần, khi tới số nguyên tố iii thì những bội 2.i,3.i,...,(i−1).i2.i, 3.i,..., (i - 1).i2.i,3.i,...,(i−1).i đều đã bị loại đi trước đó bởi những số nguyên tố nhỏ hơn iii rồi. Cũng chính nhờ điều này nên vòng lặp bên phía ngoài chỉ việc duyệt từ 222 tới NsqrtNN, giúp giảm độ phức tạp của giải thuật đi nhiều. Đánh giá độ phức tạp giải thuật: Ở một số trong những trường hợp, người ta cần tìm những số nguyên tố trên đoạn [L,R][L, R][L,R] cho trước và RRR hoàn toàn có thể lên tới 1012,10^12,1012, với điều kiện hoàn toàn có thể tạo được một mảng có độ dài (R−L+1)(R - L + 1)(R−L+1). Ý tưởng giải thuật như sau: Sàng lọc trước một mảng gồm những số nguyên tố trong đoạn [2...R][2...sqrtR][2...R], sau đó duyệt qua những số nguyên tố này, vô hiệu những bội của chúng nằm trong đoạn [L,R][L, R][L,R]. Code dưới đây tăng cấp cải tiến một chút ít để bỏ bớt bước tạo mảng số nguyên tố trong đoạn [2...R],[2...sqrtR],[2...R], nhằm mục đích tiết kiệm thời gian chạy. Như vậy với một số trong những XXX trong đoạn [L,R],X[L, R], X[L,R],X là số nguyên tố khi và chỉ khi is_prime[X−L]=truetextis_prime[X - L]=trueis_prime[X−L]=true. Thuật toán có độ phức tạp là O((R−L+1).log(R)+R)O((R - L + 1).log(R) + sqrtR)O((R−L+1).log(R)+R). Trên thực tế nó chạy khá nhanh. Vấn đề phân tích thừa số nguyên tố cũng rất được quan tâm trong lập trình thi đấu, và nó còn tồn tại một số trong những ứng dụng khác trong số học. Dưới đây tất cả chúng ta sẽ xem xét vài phương pháp phân tích thừa số nguyên tố thường dùng. Ta xét mọi số nguyên tố bắt nguồn từ 2,2,2, nếu NNN chia hết cho số nguyên tố PPP thì chia NNN cho PPP tới lúc không thể chia hết nữa, rồi tăng PPP lên và lặp lại việc làm tới khi N=1N=1N=1. Trên thực tế thừa số nguyên tố đó đó là thành phần cấu trúc nên một ước của N,N,N, do đó khi tách hết một thừa số nguyên tố XXX khỏi NNN thì NNN sẽ không thể chia hết cho những bội to hơn XXX nữa. Cài đặt: Xuất phát từ nhận xét sau: Không thể xảy ra trường hợp mọi thừa số nguyên tố của NNN đều to hơn N,sqrtN,N, do đó tất cả chúng ta chỉ việc xét những ước của NNN từ 222 tới NsqrtNN và chia dần NNN cho những ước của nó tới khi NNN bằng 111. Nếu không thể tìm được ước nào từ 222 tới NsqrtNN thì NNN phải là một số trong những nguyên tố. Độ phức tạp giải thuật là O(N)O(sqrtN)O(N). Cài đặt: Từ hai giải thuật trên ta thấy: Ở từng bước phân tích cần tìm ra ước nguyên tố nhỏ nhất của NNN rồi chia NNN cho ước đó. Ta sẽ thay đổi sàng Eratosthenes đi một chút ít để lấy được ngay ước nguyên tố nhỏ nhất của NNN trong O(1)O(1)O(1) ở từng bước phân tích, điều này sẽ giúp giảm thời gian chạy đi đáng kể. Cài đặt: Mặc dù việc thực hiện sàng Eratosthenes vẫn mất O(N.logN),O(N.logN),O(N.logN), tuy nhiên thao tác phân tích một số trong những PPP thành thừa số nguyên tố chỉ mất độ phức tạp O(logP)O(logP)O(logP). Điều này sẽ rất có lợi trong những bài toán phải phân tích thừa số nguyên tố nhiều lần. Giả sử ta phân tích được NNN thành những thừa số nguyên tố ở dạng: N=p1k1×p2k2×...×pmkmN=p_1^k_1times p_2^k_2times ... times p_m^k_m
N=p1k1×p2k2×...×pmkm Các ước số của NNN sẽ phải có dạng: p1r1×p2r2×...×pmrmp_1^r_1times p_2^r_2times ...times p_m^r_m
p1r1×p2r2×...×pmrm với 0≤r1≤k1,0≤r2≤k2,...,0≤rm≤km0 le r_1 le k_1, 0 le r_2 le k_2,..., 0 le r_m le k_m0≤r1≤k1,0≤r2≤k2,...,0≤rm≤km. Theo nguyên tắc nhân, ta thấy: r1r_1r1 có k1+1k_1 + 1k1+1 cách chọn, r2r_2r2 có k2+2k_2 + 2k2+2 cách chọn,..., rmr_mrm có km+1k_m + 1km+1 cách chọn. Như vậy số lượng ước của NNN sẽ được tính theo công thức: FN=(k1+1)×(k2+1)×...×(km+1)F_N=(k_1+1)times (k_2+1) times ... times (k_m+1)
FN=(k1+1)×(k2+1)×...×(km+1) Từ đây, ta có ý tưởng đếm số ước của một số trong những nguyên dương N như sau: Cài đặt: Bạn đọc hãy tự suy nghĩ thêm cách sử dụng sàng Eratosthene để đếm số ước của số nguyên dương N,N,N, sẽ rất hữu dụng trong những bài toán cần đếm nhanh số ước của NNN. Định lý: Nếu một số trong những nguyên dương NNN khi phân tích ra thừa số nguyên tố có dạng: N=p1k1×p2k2×...×pmkm (ki≠0;∀i:1≤i≤m)N=p_1^k_1times p_2^k_2times ... times p_m^k_m text (k_i ne 0; forall i: 1 le i le m)N=p1k1×p2k2×...×pmkm (ki=0;∀i:1≤i≤m) thì tổng những ước nguyên dương của nó được tính theo công thức: σ(N)=∏i=1k(pimi+1pi−1)sigma(N) = prod_i = 1^k (fracp_i^m_i + 1p_i - 1)
σ(N)=i=1∏k(pi−1pimi+1) Chứng minh: Các ước số của NNN sẽ phải có dạng: p1r1×p2r2×...×pmrmp_1^r_1times p_2^r_2times ...times p_m^r_m
p1r1×p2r2×...×pmrm với 0≤r1≤k1,0≤r2≤k2,...,0≤rm≤km0 le r_1 le k_1, 0 le r_2 le k_2,..., 0 le r_m le k_m0≤r1≤k1,0≤r2≤k2,...,0≤rm≤km. →rightarrow→ Tổng những ước của NNN là: σ(N)=∑r1=0k1∑r2=0k2⋯∑rm=0km(p1r1×p2r2×⋯×pmrm=∑r1=0k1p1r1×∑r2=0k2p2r2×⋯×∑rm=0kmpmrm (1)sigma(N) = sum_r_1=0^k_1 sum_r_2=0^k_2 cdots sum_r_m = 0^k_m (p_1^r_1 times p_2^r_2 times cdots times p_m^r_m = sum_r_1=0^k_1 p_1^r_1 times sum_r_2=0^k_2 p_2^r_2 times cdots times sum_r_m=0^k_m p_m^r_m (1)σ(N)=∑r1=0k1∑r2=0k2⋯∑rm=0km(p1r1×p2r2×⋯×pmrm=∑r1=0k1p1r1×∑r2=0k2p2r2×⋯×∑rm=0kmpmrm (1) Mà ta có công thức dãy cấp số nhân sau: p0+p1+p2+...+pn=pn+1−1p−1 (2)p^0 + p^1 + p^2 +...+ p^n = fracp^n + 1 - 1p - 1 (2)
p0+p1+p2+...+pn=p−1pn+1−1 (2) Từ (1)(1)(1) và (2)(2)(2), ta có: σ(N)=p1k1+1−1p1−1×p2k2+1−1p2−1×⋯×pmkm+1−1pm−1sigma(N) = fracp_1^k_1 + 1 - 1p_1 - 1 times fracp_2^k_2 + 1 - 1p_2 - 1 times cdots times fracp_m^k_m + 1 - 1p_m - 1
σ(N)=p1−1p1k1+1−1×p2−1p2k2+1−1×⋯×pm−1pmkm+1−1 Cài đặt: Tương tự, bạn đọc hãy tự suy nghĩ cách tăng cấp cải tiến việc phân tích thừa số nguyên tố bằng sử dụng sàng lọc eratosthene, trong những bài toán multitest sẽ cực kỳ hữu dụng về mặt tối ưu thời gian chạy.II. Sàng lọc số nguyên tố Eratosthenes
2. Cài đặt giải thuật
Với i=2i = 2i=2, vòng lặp bên trong lặp N2fracN22N lần.
Với i=3i = 3i=3, vòng lặp bên trong lặp N3fracN33N lần.
Với i=5i = 5i=5, vòng lặp bên trong lặp N5fracN55N lần.
.........
Tổng số lần lặp sẽ là N.(12+13+15+...)N.(frac12+frac13+frac15+...)N.(21+31+51+...), độ phức tạp sẽ tiến tới O(N.log(N))O(N.log(N))O(N.log(N)).
3. Sàng số nguyên tố trên đoạn
III. Phân tích thừa số nguyên tố
1. Giải thuật cơ sở
2. Cải tiến lần 1
3. Phân tích thừa số nguyên tố bằng sàng Eratosthenes:
4. Đếm số ước của một số trong những nguyên
Phân tích NNN thành thừa số nguyên tố.
Đặt một biến cnt_xtextcnt_xcnt_x là số lần xuất hiện của thừa số nguyên tố xxx trong phân tích của NNN. Ta vừa phân tích NNN vừa update số lượng thừa số nguyên tố lên biến cnt_xtextcnt_xcnt_x.
5. Tính tổng những ước số nguyên dương của một số trong những nguyên dương
Tài liệu tham khảo:
Video Viết chương trình xuất ra tất cả những số nguyên tố nhỏ hơn n theo thuật toán sàng eratosthène. ?
Bạn vừa tham khảo tài liệu Với Một số hướng dẫn một cách rõ ràng hơn về Video Viết chương trình xuất ra tất cả những số nguyên tố nhỏ hơn n theo thuật toán sàng eratosthène. tiên tiến nhất
Chia Sẻ Link Download Viết chương trình xuất ra tất cả những số nguyên tố nhỏ hơn n theo thuật toán sàng eratosthène. miễn phí
Hero đang tìm một số trong những Chia SẻLink Tải Viết chương trình xuất ra tất cả những số nguyên tố nhỏ hơn n theo thuật toán sàng eratosthène. miễn phí.
Giải đáp thắc mắc về Viết chương trình xuất ra tất cả những số nguyên tố nhỏ hơn n theo thuật toán sàng eratosthène.
Nếu sau khi đọc nội dung bài viết Viết chương trình xuất ra tất cả những số nguyên tố nhỏ hơn n theo thuật toán sàng eratosthène. vẫn chưa hiểu thì hoàn toàn có thể lại Comment ở cuối bài để Mình lý giải và hướng dẫn lại nha
#Viết #chương #trình #xuất #tất #cả #những #số #nguyên #tố #nhỏ #hơn #theo #thuật #toán #sàng #eratosthène - 2022-08-01 06:22:02
