Kiểm Tra Nguyên Tố

Nguồn: CLUE OJ Độ khó: Dễ Số nguyên tố Căn bậc hai

Đề bài

Cho một số nguyên dương $P$. Hãy kiểm tra $P$ có phải là số nguyên tố hay không.

Nhắc lại: một số nguyên dương được gọi là số nguyên tố khi và chỉ khi nó lớn hơn 1 và không chia hết cho số nguyên nào khác ngoài 1 và chính nó. Ví dụ $2, 3, 5, 7, 11, 13$ là số nguyên tố; $1, 4, 6, 9, 62$ không phải số nguyên tố.

Input: Một dòng duy nhất chứa số nguyên dương $P$ $(1 \le P \le 10^{14})$.

Output: In ra YES nếu $P$ là số nguyên tố, ngược lại in ra NO.

Ràng buộc (theo bộ test 100 test trên CLUE OJ):

• 30% số test có $P \le 10^6$;
• 15% số test tiếp theo có $10^6 < P \le 10^9$;
• 55% số test còn lại có $P \le 10^{14}$.

Ví dụ – input

3

Ví dụ – output

YES

Thêm vài ví dụ để tự kiểm tra: $P = 62$ → NO (vì $62 = 2 \times 31$); $P = 97$ → YES; $P = 1$ → NO (1 không phải số nguyên tố).

Lời mở đầu

Đây là bài nền tảng nhất của chủ đề số nguyên tố, gần như năm nào đề thi học sinh giỏi cũng có một câu cần dùng tới hàm kiểm tra nguyên tố. Bài này cũng là Câu 1 trong đề mô phỏng HSG Tin học THPT tỉnh Thanh Hóa, nên mình viết thật chậm, thật kỹ để các em nắm chắc và lấy trọn điểm 😇.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Vét cạnThử mọi sốNhận xétChỉ cần tới √P100%Thử chia đến √PMẹoBỏ số chẵn

Vét cạnThử chia P cho mọi số từ 2 đến P − 1

Làm đúng theo định nghĩa: $P$ là số nguyên tố khi $P \ge 2$ và không có số nào trong khoảng từ $2$ đến $P - 1$ chia hết $P$. Vậy ta cho biến $i$ chạy từ $2$ đến $P - 1$, gặp số nào chia hết ($P \bmod i = 0$) thì kết luận ngay $P$ không phải số nguyên tố và dừng vòng lặp.

• Phải dùng kiểu long long vì $P$ có thể tới $10^{14}$, vượt xa giới hạn của int (khoảng $2 \cdot 10^9$).
• Đừng quên trường hợp $P = 1$: vòng lặp không chạy lần nào, nên phải gán sẵn laNguyenTo = (p >= 2) để 1 cho ra NO.

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long p;
    cin >> p;
    bool laNguyenTo = (p >= 2);
    for(long long i = 2; i < p; i++){
        if(p % i == 0){
            laNguyenTo = false;
            break;
        }
    }
    cout << (laNguyenTo ? "YES" : "NO");
    return 0;
}

p = int(input())
la_nguyen_to = p >= 2
for i in range(2, p):
    if p % i == 0:
        la_nguyen_to = False
        break
print("YES" if la_nguyen_to else "NO")

C++▶ Chạy tay từng dòng codeVét cạn: thử chia p cho mọi số i từ 2 đến p − 1.

Dữ liệu vào (stdin) – sửa thoải mái3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 long long p;

6 cin >> p;

7 bool laNguyenTo = (p >= 2);

8 for(long long i = 2; i < p; i++){

9 if(p % i == 0){

10 laNguyenTo = false;

11 break;

12 }

13 }

14 cout << (laNguyenTo ? "YES" : "NO");

15 return 0;

16}

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

Thời gian$O(P)$

Cách này đúng nhưng chậm. Nếu $P$ là số nguyên tố lớn, ví dụ $P \approx 10^{14}$, vòng lặp phải chạy gần $10^{14}$ lần, trong khi 1 giây máy chỉ chạy được cỡ $10^8$ phép tính. Mình chấm thử trên bộ test thì cách vét cạn được 58/100 test: đủ hết các test $P \le 10^9$ (vì đa số các số đó nhỏ hoặc có ước nhỏ nên thoát sớm), còn các số nguyên tố lớn thì bị quá thời gian.

Nhận xétƯớc luôn đi theo cặp – chỉ cần thử tới √P

Nếu $P$ không phải số nguyên tố thì ta viết được $P = a \times b$ với $2 \le a \le b$. Khi đó $a \times a \le a \times b = P$, tức là $a \le \sqrt{P}$. Nói cách khác: nếu $P$ có ước thì nó luôn có một ước nằm trong đoạn từ $2$ đến $\sqrt{P}$. Thử hết các số trong đoạn này mà không thấy số nào chia hết thì chắc chắn $P$ là số nguyên tố.

Xem ví dụ với $36$: các ước của $36$ ghép thành từng cặp có tích bằng $36$. Số nhỏ trong mỗi cặp không bao giờ vượt quá $\sqrt{36} = 6$:

Điều kiện dừng vòng lặp

Thay vì i < p, ta cho vòng lặp chạy khi i * i <= p. Viết i * i <= p thay cho i <= sqrt(p) để tránh sai số của phép tính số thực, và vì $i \le 10^7$ nên $i \cdot i \le 10^{14}$ vẫn nằm gọn trong long long.

Số lần lặp giảm đi khủng khiếp:

P	Vét cạn (tới P − 1)	Tới √P	Tới √P, chỉ số lẻ
106	≈ 106	1.000	500
109	≈ 109	31.623	15.811
1014	≈ 1014	107	5·106

Em nhập $P$ rồi bấm Tiếp để xem từng bước thử chia, chỉ tới $\sqrt{P}$:

P =

Ví dụ nhanh:

100%Thử chia đến √P

Cài đặt đúng như nhận xét: viết hàm check(p) trả về true/false, trong main chỉ việc đọc $P$ rồi in YES hoặc NO. Tách thành hàm như vậy giúp các bài sau (đếm số nguyên tố, tổng các số nguyên tố, …) chỉ cần gọi lại hàm này.

#include <bits/stdc++.h>
using namespace std;

bool check(long long p){
    if(p < 2) return false;
    for(long long i = 2; i * i <= p; i++){
        if(p % i == 0){
            return false;
        }
    }
    return true;
}

int main(){
    long long p;
    cin >> p;
    if(check(p)) cout << "YES";
    else cout << "NO";
    return 0;
}

def check(p):
    if p < 2:
        return False
    i = 2
    while i * i <= p:
        if p % i == 0:
            return False
        i += 1
    return True

p = int(input())
print("YES" if check(p) else "NO")

C++▶ Chạy tay từng dòng codeChỉ thử chia đến √p: vòng lặp dừng khi i·i > p.

Dữ liệu vào (stdin) – sửa thoải mái97

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4bool check(long long p){

5 if(p < 2) return false;

6 for(long long i = 2; i * i <= p; i++){

7 if(p % i == 0){

8 return false;

9 }

10 }

11 return true;

12}

13

14int main(){

15 long long p;

16 cin >> p;

17 if(check(p)) cout << "YES";

18 else cout << "NO";

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

Thời gian$O(\sqrt{P})$

Với $P \le 10^{14}$ thì vòng lặp chạy tối đa $10^7$ lần, C++ chạy chưa tới 0,05 giây. Cách này đạt 100/100 test.

MẹoBỏ qua các số chẵn – nhanh gấp đôi

Ngoài số $2$ ra thì mọi số chẵn đều không phải số nguyên tố. Vậy ta xử lý riêng $P = 2$ và $P$ chẵn trước, sau đó chỉ cần thử các ước lẻ $3, 5, 7, \dots$ (mỗi bước i += 2). Số lần lặp giảm một nửa. Mẹo này đặc biệt có ích khi em làm bằng Python (chạy chậm hơn C++ nhiều lần), giúp chắc chắn không bị quá thời gian trên máy chấm yếu.

#include <bits/stdc++.h>
using namespace std;

bool check(long long p){
    if(p < 2) return false;
    if(p == 2) return true;
    if(p % 2 == 0) return false;
    for(long long i = 3; i * i <= p; i += 2){
        if(p % i == 0){
            return false;
        }
    }
    return true;
}

int main(){
    long long p;
    cin >> p;
    cout << (check(p) ? "YES" : "NO");
    return 0;
}

def check(p):
    if p < 2:
        return False
    if p == 2:
        return True
    if p % 2 == 0:
        return False
    i = 3
    while i * i <= p:
        if p % i == 0:
            return False
        i += 2
    return True

p = int(input())
print("YES" if check(p) else "NO")

C++▶ Chạy tay từng dòng codeLoại số chẵn trước, rồi chỉ thử các ước lẻ 3, 5, 7, … đến √p.

Dữ liệu vào (stdin) – sửa thoải mái97

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4bool check(long long p){

5 if(p < 2) return false;

6 if(p == 2) return true;

7 if(p % 2 == 0) return false;

8 for(long long i = 3; i * i <= p; i += 2){

9 if(p % i == 0){

10 return false;

11 }

12 }

13 return true;

14}

15

16int main(){

17 long long p;

18 cin >> p;

19 cout << (check(p) ? "YES" : "NO");

20 return 0;

21}

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

Thời gian$O(\sqrt{P}/2)$

Những lỗi hay gặp khiến mất điểm

• Dùng int để đọc $P$ → tràn số với các test lớn. Phải dùng long long.
• Quên $P = 1$ → in nhầm YES. Luôn kiểm tra p < 2 trước.
• Viết i <= sqrt(p) với số thực có thể bị sai số ở số rất lớn → nên viết i * i <= p.
• In sai chữ: đề yêu cầu YES/NO in hoa, không thêm dấu cách hay chữ khác.
• Khi thi trên Themis theo đề mô phỏng: nhớ đọc từ tệp CAU1.INP và ghi ra tệp CAU1.OUT.

Ghi chú kiểm tra của mình: cả 3 bản C++ và 3 bản Python đã được mình biên dịch, chạy lại trên đủ 100 test của CLUE OJ. Cách thử chia đến √P và cách bỏ số chẵn đều đạt 100/100 test: C++ tối đa 0,03 giây mỗi test, Python tối đa 0,77 giây (thử đến √P) và 0,41 giây (chỉ số lẻ). Cách vét cạn đạt 58/100 test, các test còn lại quá 1 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇