Số nguyên tố là số rất thường xuất hiện trong các bài toán học và tin học. Trong bài viết này, chúng mình sẽ giúp các bạn hiểu được bản chất của số nguyên tố và kiểm tra xem một số bất kì có phải là số nguyên tố hay không bằng các phương pháp cơ bản và phổ biến nhất. Qua đó các bạn có thể giải quyết hiệu quả các bài tập liên quan đến số nguyên tố.
1. Khái niệm
Số nguyên tố (Prime number) là số tự nhiên lớn hơn $1$ chỉ có đúng hai ước số là $1$ và chính nó. Ví dụ: $2, 3, 5, 7, 11, 13, 17,$ ... là những số nguyên tố.
Hợp số (Composite number) là số tự nhiên lớn hơn $1$ và có nhiều hơn $2$ ước. Ví dụ: $4, 9, 15, 27, 111,$ ... là những hợp số.
2. Cài đặt
Đề bài: Xét một số nguyên dương $N$ xem số đó có phải là số nguyên tố hay không.
2.1 Cài đặt ngây thơ
Nhận xét
Ta dựa vào tính chất đã nêu trên để xét. Cụ thể, ta thử chia hết $N$ cho các số từ $2$ đến $N- 1$ để tìm các ước, nếu có $1$ ước trở lên thì $N$ không phải là số nguyên tố.
Code mẫu
bool isPrime(int n) {
for(int i = 2; i < n; i++) {
if(n % i == 0) { // nếu tìm được một ước thì nó không là số nguyên tố
return 0;
}
}
return n > 1;
}
Độ phức tạp
Độ phức tạp thời gian: $\mathcal{O}(n)$
Độ phức tạp không gian: $\mathcal{O}(1)$
2.2 Cải tiến
Nhận xét
Ta nhận thấy rằng nếu $N$ không phải là số nguyên tố, $N$ có dạng $N=A \cdot B$ và hiển nhiên $A,B$ không thể cùng lớn hơn $\sqrt{N}$ vì nếu như vậy thì $A \cdot B > \sqrt{N} \cdot \sqrt{N}=N$. Vậy nên trong các ước số của $N$ thì ít nhất một trong các ước sẽ nhỏ hơn $\sqrt{N}$. Tóm lại, ta chỉ cần xét từ $2$ đến $\sqrt{N}$, nếu có ước trong đoạn này thì $N$ không phải là số nguyên tố .
Code mẫu
bool isPrime(long long n) {
for(int i = 2; i * i <= n; i++) { // chạy đến căn của n
if(n % i == 0) { // nếu tìm được một ước thì nó không là số nguyên tố
return 0;
}
}
return n > 1;
}
Độ phức tạp
Độ phức tạp thời gian: $\mathcal{O}(\sqrt{n})$
Độ phức tạp không gian: $\mathcal{O}(1)$
3. Sàng Eratosthenes (Sieve of Eratosthenes)
3.1 Khái niệm
Sàng Eratosthenes dùng để tìm các số nguyên tố nhỏ hơn hoặc bằng số nguyên $N$ nào đó.
Nguyên lí hoạt động của sàng là vào mỗi lần duyệt, ta chọn một số nguyên tố và loại ra khỏi sàng tất cả các bội của số nguyên tố đó mà lớn hơn số đó. Sau khi duyệt xong, các số còn lại trong sàng đều là số nguyên tố.
3.2 Code mẫu
vector <bool> prime(n + 1, true); // khởi tạo mảng prime với giá trị true
for (int i = 2; i * i <= n; i++) {
if (prime[i] == true) { // nếu i là số nguyên tố
for (int j = i * i; j <= n; j += i) { // thì loại bỏ các số là bội của i
prime[j] = false;
}
}
}
Độ phức tạp
Độ phức tạp thời gian: $\mathcal{O}(n\log{n})$
Độ phức tạp không gian: $\mathcal{O}(n)$
Ứng dụng
Sàng Eratosthenes rất hữu dụng cho các bài tìm số nguyên tố nhiều truy vấn vì khi khởi tạo xong chỉ tốn $\mathcal{O}(1)$ cho từng lần kiểm tra.
Kết hợp với mảng cộng dồn ta có thể dễ dàng tính được số lượng số nguyên tố trên đoạn $l$ đến $r$.
4. Tìm hiểu thêm
- Thuật toán Miller - Rabin
- Phép thử Fermat
5. Bài tập làm thêm
Nguồn tham khảo
NGĂM X CLAOJ : CHARITY CODING MARATHON “ĐƯỜNG ĐẾN LA NGÂU” - PHASE 2
posted on July 23, 2023, 8:46 p.m. 0🌻Ngăm và CLAOJ xin trân trọng cảm ơn sự hỗ trợ của anh Nguyễn Đức Thuận - một trong những cá nhân tiêu biểu trong cộng đồng lập trình thi đấu Việt Nam.
🌻Tính đến thời điểm hiện tại, cuộc thi Charity Coding Marathon “Đường đến La Ngâu” của Ngăm x CLAOJ đã được sự tham gia nhiệt liệt của các bạn. Chúng mình rất lấy làm biết ơn vì sự ủng hộ ấy. Chúng mình xin được phép cập nhật thêm một số thông tin về Phase ~2~ của cuộc thi:
🌻Link contest: https://claoj.edu.vn/contest/claoj_ngam
- Các bài tập trong đợt ~2~ của contest sẽ có độ khó cao hơn đợt ~1~.
- Nhằm để contest thêm phần kịch tính và hấp dẫn, chúng mình sẽ bổ sung bài mới theo từng ngày. Cụ thể:
- Ngày thứ nhất ~(24/7)~ chúng mình sẽ đăng ~2~ bài.
- Các ngày còn lại, mỗi ngày lúc ~8:00~ chúng mình sẽ đăng thêm ~1~ hoặc ~2~ bài tập cho đến hết ngày ~26/7~.
- Các bài tiếp theo sẽ có số điểm ~> 100~.
- Cập nhật về việc góp quỹ: Mỗi bài nộp AC ứng với ~7.000~đ được góp vào quỹ Chuyến đi Nắng của Ngăm. Điều này cũng được áp dụng với các bài tập ở Phase ~1~. (~5.000~đ của CLAOJ và ~2.000~đ do anh Nguyễn Đức Thuận tài trợ).
🌻Xin chào các thành viên của CLAOJ. Nhận thấy sự cần thiết về việc giúp đỡ các em nhỏ trước thềm năm học mới cùng với sự hưởng ứng nhiệt tình của các thí sinh ở các kì thi trước, chúng mình đã quyết định tổ chức một kì thi hoàn toàn mới, thú vị và đầy ý nghĩa mang tên NGĂM X CLAOJ: CHARITY CODING MARATHON .🌻
Sứ mệnh đằng sau cuộc thi này không chỉ dừng lại ở việc thử thách và phát triển tài năng lập trình mà còn hướng tới mục tiêu cao cả hơn, đó là gây quỹ cho tổ chức thiện nguyện NGĂM để giúp đỡ các em học sinh đang sinh sống tại vùng núi xã La Ngâu, huyện Tánh Linh, tỉnh Bình Thuận.
🌻Với mỗi bài nộp AC (Đáp án đúng), CLAOJ sẽ góp ~5.000~ đồng vào quỹ Chuyến đi Nắng của NGĂM.🌻
Link contest: https://claoj.edu.vn/contest/claoj_ngam
Sau đây là một số thông tin về kì thi:
- Ban ra đề: , , , , , , . Ban ra đề bao gồm thành viên đạt giải HSGQG, thành viên đạt giải Tin học trẻ khu vực & toàn quốc, thành viên đạt huy chương OLP ~30/4~, cựu đội tuyển HSGQG môn Tin học tỉnh Long An.
- Thời gian: ~8:00~ - Thứ ~6~, ngày ~21~ tháng ~7~ năm ~2023~
- Thời lượng: ~7~ ngày
- Lượng bài tập: ~10~ bài, chia làm hai đợt:
- Đợt ~1~ ~(21/7)~ gồm ~5~ bài với độ khó dễ, trung bình.
- Đợt ~2~ ~(24/7)~ gồm thêm ~5~ bài với độ khó trung bình, khó.
- Kì thi sẽ tính rating cho tất cả thí sinh tham gia
- Tổng số tiền quyên góp sẽ được công khai ngay sau khi kì thi kết thúc
Lưu ý: Các hành vi chép code, gian lận dưới mọi hình thức sẽ bị loại khỏi kì thi và cấm tài khoản khỏi trang web.
🌟Chúc các bạn có một kì thi vui vẻ và bổ ích! 💖
Happy coding, CLAOJ.
Xin chào các thành viên của CLAOJ, bài viết đầu tiên của chuỗi bài viết về lập trình sẽ giúp các bạn cài đặt các phần mềm cần thiết để phục vụ cho quá trình học Tin học. Ở bài viết này chúng mình sẽ hướng dẫn cài đặt Code::Blocks để lập trình ngôn ngữ C++. Code::Blocks được sử dụng nhiều bởi tính tiện lợi, dễ cài đặt và dễ sử dụng của nó.
Cài đặt
- Tải Code::Blocks (với máy 32bit, tải ở đây)
- Chạy file cài đặt, nhấn NEXT và I AGREE, chọn hết tất cả các tùy chỉnh. Ở phần chọn đường dẫn cài đặt, chúng mình khuyên các bạn để mặc định để thuận tiện cho việc cá nhân hóa ở cuối bài viết.
Xin chào các thành viên của CLAOJ. Nhằm tạo ra một sân chơi lập trình bổ ích và thú vị, chúng mình sẽ tổ chức CLAOJ Beginner Contest lần đầu tiên vào ngày 4/6 sắp tới đây. Đây là contest mở đầu chuỗi kì thi dành cho các bạn học sinh cấp 2, hay các bạn nhập môn lập trình thi đấu. Đặc biệt, các bạn đạt thành tích tốt trong kì thi này sẽ nhận được phần thưởng từ ban tổ chức (cụ thể bên dưới).
Link contest: https://claoj.edu.vn/contest/claojbc1
Sau đây là một số thông tin về kì thi:
- Ban ra đề: , , ,
- Thời gian: $19:30$ - $22:00$ Chủ nhật, ngày $4$ tháng $6$ năm $2023$.
- Thời lượng: $2$ tiếng $30$ phút.
- Lượng bài tập: $4$ bài.
- Kì thi sẽ có tính rating dành cho các bạn có rating dưới 1900 (từ Expert trở xuống).
- Cơ cấu giải thưởng:
- Top 1: $50\,000$ đồng
- Top 2: $30\,000$ đồng
- Top 3: $20\,000$ đồng
- Hình thức phát thưởng: chuyển khoản ngân hàng hoặc Momo.
Lưu ý: Các hành vi chép code, gian lận dưới mọi hình thức sẽ bị loại khỏi kì thi và cấm tài khoản khỏi trang web.
Chúc các bạn có một kì thi vui vẻ và bổ ích!
UPD: Kì thi đã kết thúc, chúng mình xin cảm ơn các bạn đã nhiệt tình tham gia kì thi. Chúng mình xin chúc mừng các bạn đã có thành tích tốt và nhận thưởng trong kì thi lần này:
- - 400 điểm
- - 400 điểm
- - 400 điểm
Các bạn , , hãy liên hệ page It-Cla Productions để nhận thưởng từ chúng mình nhé!
Hẹn gặp lại các bạn ở những kì thi sắp tới!
Happy coding, CLAOJ.
Xin chào các thành viên của CLAOJ. Nhằm hỗ trợ các bạn học sinh trong việc luyện tập lập trình thi đấu, chúng mình rất hào hứng thông báo rằng sắp tới chúng mình sẽ ra mắt một chuỗi các bài viết về lập trình thi đấu trên website. Thông qua chuỗi bài viết này, chúng mình muốn trang bị cho các bạn những kiến thức và kĩ thuật hữu ích trong các cuộc thi Tin học như Học sinh giỏi, Tin học trẻ.
Các bài viết sẽ được viết bởi các bạn học sinh/cựu học sinh đội tuyển Tin học có kinh nghiệm, đi kèm với hướng dẫn chi tiết và hình ảnh minh họa để mang kiến thức đến các bạn một cách trực quan và chính xác nhất. Chuỗi bài viết dự kiến sẽ bắt đầu từ ngày 10/6 và sẽ được đăng liên tục hằng tuần để đảm bảo kiến thức mới luôn được cập nhật. Trình tự của các bài đăng cũng sẽ có độ khó tăng dần nhằm phù hợp với mọi đối tượng.
Để đảm bảo không bỏ lỡ bất kì bài viết nào, hãy theo dõi Fanpage It-Cla Productions để luôn nhận được thông báo mỗi khi có cập nhật về bài viết mới. Chúng mình mong sẽ nhận được những phản hồi tích cực của các bạn xuyên suốt chuỗi bài viết này. Qua đó góp phần nâng cao chất lượng bài viết tại CLAOJ.
Happy coding, CLAOJ.