Hướng Dẫn Cho Đếm Số Nguyên Tố - LQDOJ
Có thể bạn quan tâm
Tiếng Việt
Tiếng Việt EnglishĐăng nhập
Đăng ký
Hướng dẫn cho Đếm số nguyên tố
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này. Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.Authors: SPyofgame
\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)
\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)
\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây
\(\color{#300000}{\text{Hint 1 <Cày trâu>}}\)
-
Với mỗi truy vấn \(l, r\) ta sẽ duyệt qua đoạn \(l, r\) và kiểm tra xem có bao nhiêu số nguyên tố
-
Việc kiểm tra có thể dùng thuật toán \(miller-rabin\) trong \(O(polylog(p)) \approx O(log^4(p))\) hoặc duyệt \(O(\sqrt{p})\)
-
Gọi \(O(query())\) là độ phức tạp trả lời truy vấn, \(O(check())\) là độ phức tạp hàm kiểm tra
-
Độ phức tạp thời gian tổng thể cách này sẽ là \(O(q) \times O(query(max\_val)) \times O(check(max\_val))\)
\(\color{#300000}{\text{Hint 2 <Tiền xử lí>}}\)
-
Mình sẽ tiền xử lí đánh dấu các số nguyên tố, lúc này ta có thể kiểm tra các số nguyên tố trong \(O(1)\)
-
Gọi \(O(precal())\) là độ phức tạp hàm tiền xử lí
-
Độ phức tạp thời gian tổng thể của cách này sẽ là \(O(q) \times O(query(max\_val)) \times O(1) + O(precal(max\_val))\)
\(\color{#300000}{\text{Hint 3 <Sàng nguyên tố>}}\)
- Cách đánh dấu cơ bản là mình duyệt từng số \(x\) trong đoạn \([1, max\_val]\) và kiểm tra xem nếu nó chỉ có 2 ước \(d\) nguyên dương là \(d_1 = 1\) và \(d_2 = x\)
Cách này có độ phức tạp là \(O(precal()) = O(max\_val \times O(check())\)
\(\rightarrow\) Độ phức tạp tổng thể \(O(q \times max\_val \times O(1) + max\_val \times O(check()) = O(max\_val \times (q + O(check()))\)
- Thay vì thử tìm các ước, ta sẽ thử đánh dấu các bội, có nghĩa là với mỗi số nguyên tố, ta sẽ đánh dấu tất cả bội của nó sẽ không còn là số nguyên tố nữa
Chứng minh: Gọi \(p\) là số nguyên tố đang xét, thì các bội của nó \(x \times p\) với \((x \in \mathbb{N^*}, x > 1)\) sẽ có ít nhất 3 ước \(d\) là \(\{1, p, x \times p\}\) nên sẽ không phải là số nguyên tố
- Ta sẽ không cần đánh dấu các bội của số nguyên tố quá giá trị \(max\_val\)
Chứng minh: mình chỉ cần đánh dấu các bội trong khoảng \([1, max\_val]\), những số lớn hơn không ảnh hưởng tới việc đánh dấu (vì bội của các số đang xét luôn lớn hơn chính nó nên không có trường hợp mình xét các số nhỏ hơn)
- Trong quá trình duyệt từ số nguyên tố \(p = 2 \rightarrow max\_val\), những số chưa bị đánh dấu sẽ là số nguyên tố
Chứng minh: Nếu \(p\) chưa bị đánh dấu thì \(p\) không có ước nguyên tố nào trong đoạn \([2, p - 1]\) nên \(p\) chỉ có duy nhất 2 ước nguyên dương là \(\{1, p\}\) \(\Rightarrow\) \(p\) là số nguyên tố
- Mỗi lần duyệt một số \(p\), chi phí để duyệt qua bội của nó là \(O(\frac{n}{p})\) với \(p\) nguyên tố và \(O(1)\) với \(p\) hợp số nên \(O(precal()) = O(n \log \log n)\)
Chứng minh: (cp-algorithms), link tới chứng minh cụ thể hơn - p349
Có \(O(precal()) = O(n) + O(\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} + \dots) = O(n) + O(n) \times O(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots)\)
Mà \(\frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots = \underset{\underset{\text{prime p}}{p \leq n}}{\Sigma}\frac{1}{p} \approx \sum_{k = 2}^{\frac n {\ln n}} \frac 1 {k \ln k} \approx \int_2^{\frac n {\ln n}} \frac 1 {k \ln k} dk =\ln \ln \frac n {\ln n} - \ln \ln 2 = \ln(\ln n - \ln \ln n) - \ln \ln 2 \approx \ln \ln n\)
Nên ta có \(O(precal()) = O(n) + O(n) \times O(\frac{1}{2} + \ln \ln n) = O(n \log \log n)\)
- Độ phức tạp thơi gian tổng thể là \(O(q) \times O(query(max\_val)) + O(n \log \log n)\)
\(\color{#300000}{\text{Hint 4 <Chặt nhị phân>}}\)
- Gọi \(prime[]\) là danh sách các số nguyên tố sắp xếp tăng dần sau khi sàng, mình cần trả lời \(q\) truy vấn đếm số nguyên tố trong đoạn \([l, r]\)
Khi \(l > r\) thì kết quả là \(0\), ngược lại ta có:
Gọi vị trí số nguyên tố nhỏ nhất lớn hơn \(l\) là \(p_1\)
Gọi vị trí số nguyên tố nhỏ nhất lớn hơn \(r\) là \(p_2\) \(\Rightarrow\) vị trí số nguyên tố lớn nhất nhỏ hơn \(r\) là \(p_2 - 1\)
\(\Rightarrow\) số nguyên tố trong đoạn \(l, r\) là \((p_2 - 1) - p_1 + 1 = p_2 - p_1\)
-
Việc chặt nhị phân mất \(O(query()) = O(\log_2 (prime.size)) = O(\log_2(\frac{n}{\ln{n}}))\)
-
Độ phức tạp thơi gian tổng thể là \(O(q) \times O(\log_2(\frac{n}{\ln{n}})) + O(n \log \log n)\)
\(\color{#300000}{\text{Hint 5 <Quy hoạch động>}}\)
- Gọi \(f[0..n]\) là số lượng số nguyên tố trong đoạn \([0..n]\)
\(\Rightarrow\) số lượng số nguyên tố trong đoạn \([l..r]\) là \(f[l..r] = f[0..r] - f[0..l - 1]\)
Ta sẽ trả lời truy vấn \(O(query()) = O(1)\) nhưng sẽ mất \(O(n)\) bộ nhớ
- Công thức quy hoạch động:
\(f[0..x] = 0\) với \(x \leq 1\)
\(f[0..x] = f[x - 1] + 1\) với \(x\) nguyên tố
\(f[0..x] = f[x - 1] + 0\) với \(x\) hợp số
- Độ phức tạp thơi gian tổng thể là \(O(q) + O(n \log \log n)\)
\(\color{#300000}{\text{Hint 6 <Tối ưu hóa>::<Constant Optimization>}}\)
Viêc tối ưu hóa hằng số có thể giúp nó nhanh lên rất nhiều lần và tất cả những cải tiến dưới đây có thể gộp vào 1
- Chỉ duyệt các số lẻ từ \(p = 3\) sau khi các số chẵn ngoại trừ số \(2\) sẽ được đánh dấu trước
Chứng minh: Tất cả số chẵn đều là bội của \(2\), mà \(2\) là số nguyên tố chẵn duy nhất nên các số nguyên tố còn lại đều lẻ
- Khi \(p^2 > n\) thì không cần xét và \(break\) ngay
Chứng minh: Nếu \(p^2 > n\) thì \((p + x)^2 > n\ (\forall x \in \mathbb{N})\) mà ta chỉ đang đánh dấu các số nguyên tố trong đoạn \([1, n]\)
- Thay vì kiểm tra \(p^2 \leq n\) ta cũng có thể kiểm tra \(p \leq sqrtn\) với \(sqrtn = \sqrt{n}\) đã được tính trước và không cần tính lại
Chứng minh: Việc tính đi tính lại \(p^2\) trong \(n\) lần chậm hơn là 1 lần tính \(\sqrt{n}\) và kiểm tra \(p \leq sqrtn\) trong \(n\) lần
- Thay vì duyệt các bội \(p\) từ \(2p, 3p, \dots\) thì ta sẽ duyệt từ \(p \times p, (p + 2) \times p, (p + 4) \times p\)
Chứng minh:
Các số có dạng \((p + 2k + 1) \times p\) là số chẵn và đã được đánh dấu là bội của \(p_0 = 2\)
Các số từ \(2p \dots (p - 1)\) đã được đánh dấu bởi các số nguyên tố nhỏ hơn \(p\)
- Chúng ta không cần sắp xếp lại mảng số nguyên tố mà có thể duyệt các giá trị từ nhỏ đến lớn và kiểm tra tính nguyên tố rồi chèn vào
\(\color{#300000}{\text{Hint 7 <Tối ưu hóa>::<Time Optimization>}}\)
Chúng ta có thể giảm độ phức tạp lí thuyết xuống thời gian tuyến tính
- Gọi \(prime[]\) là danh sách các số nguyên tố và \(lpf[x]\) là ước nguyên tố nhỏ nhất của \(x\) thì mình chỉ cần duyệt qua các \(prime[i] \times p\) thỏa (\(prime[i] \times p \leq n\) và \(prime[i] \leq lpf[p]\))
Chứng minh:
Nếu \(prime[i] \times p > n\) thì không cần xét
Nếu \(prime[i] > lpf[p]\) thì nó sẽ làm các số bị duyệt trùng
- Chúng ta có thể sàng trên từng đoạn \(O(\sqrt n)\) để sàng nhanh hơn và dùng bitwise để đẩy nhanh tốc độ tính toán bằng cách sàng từng đoạn \(O(\sqrt n) \approx O(2^15) \approx O(CPU\_cache)\)
\(\color{#300000}{\text{Hint 8 <Tối ưu hóa>::<Space Optimization>}}\)
-
Việc dùng mảng boolean rất lãng phí trong C++ vì nó chỉ lưu 2 trạng thái \(\{0, 1\}\) trong khi nó lưu trữ 1 byte (= 8 bit = \(2^8\) trạng thái)$
-
Chúng ta có thể dùng bitset<size> hoặc std::vector<bool> hoặc unsigned int array[] để đánh dấu các số với độ phức tạp \(O(\frac{n}{8})\) bằng bitwise. Vì lúc này ta tận dụng hiệu quả đến từng bit
-
Chúng ta có thể giảm một nửa mảng đánh dấu bằng việc chuyển giá trị \([x]\) lưu vào \([\lfloor \frac{x}{2} \rfloor]\)
\(2\) và \(3\) là 2 số nguyên tố lưu chung vào \([1]\)
Những số chẵn khác 2 đều không phải số nguyên tố
Những số lẻ \(p\) có \(isPrime[\frac{p - 1}{2}] = \{0, 1\}\) là \(\{\)hợp số, số nguyên tố\(\}\)
- Chúng ta có thể sàng trên từng đoạn \(O(\sqrt n)\) với \(O(\sqrt n)\) bộ nhớ chính, \(O(\frac{n}{ln n})\) để lưu số nguyên tố
Bình luận
Từ khóa » đếm Xem Trong Mảng Có Bao Nhiêu Số Nguyên Tố
-
Cách đếm Số Lượng Số Nguyên Tố Có Trong Mảng Bằng Code C++
-
Đếm Số Nguyên Tố Có Trong Mảng Một Chiều Các Số Nguyên Bằng C
-
Đếm Số Lượng Số Nguyên Tố Trong Mảng Lập Trình C/C++
-
Đếm Số Lượng Số Nguyên Tố Có Trong Mảng C
-
Đếm Trong Dãy N Có Bao Nhiêu Số Nguyên Tố - Cộng đồng C Việt
-
Viết Hàm De Quy đếm Xem Trong Dãy Có Bao Nhiêu Số Nguyên To
-
Viết Hàm đếm Các Phần Tử Là Số Nguyên Tố Trong Mảng. - How Kteam
-
Cách đếm Số Lượng Số Nguyên Tố Có Trong Mảng ... - MarvelVietnam
-
Top 14 đếm Số Nguyên Tố Trong Mảng C++
-
Đếm Số Nguyên Tố Có Trong Mảng Một Chiều Các Số Nguyên Bằng C ...
-
4 [Bài Tập C ( Mảng)]. Đếm Cặp Số Nguyên Tố Cùng Nhau - YouTube
-
Tài Liệu đếm Xem Trong Mảng Có Bao Nhiêu Số Nguyên Tố - 123doc
-
Đếm Số Nguyên Tố Trong Mảng - Tài Liệu - 123doc
-
Đếm Xem Từ 1 đến N Có Bao Nhiêu Số Nguyên To - LuTrader
-
Đếm Số Nguyên Tố Giải Pháp Leetcode - TutorialCup
-
Đếm Xem Trong Mảng Có Bao Nhiêu Số Nguyên Tố Có Sử Dụng Hàm
Cái này có sàng được đến 1e9 mà không bị quá bộ nhớ k nhỉ?
sol này viết hay (chỉ có duy nhất chỗ tính độ phức tạp bị khủng bố thôi)
1 phản hồivíp quá anh ơi, mở mang tầm mắt
1 phản hồicho em hỏi prime.assign(1, 2); là gì ạ
4 phản hồiAnh bổ sung thêm cái này https://www.geeksforgeeks.org/bitwise-sieve/ đi a :))
1 phản hồiCảm ơn ad đã viết sol nhé @@
1 phản hồi