Phân tích ra thừa số nguyên tố







Bài toán 1: Kiểm tra tính nguyên tố

1. Xác định bài toán

- Input: N là một số nguyên dương

- Output:

+ N là số nguyên tố hoặc

+ N không là số nguyên tố

- Định nghĩa: "Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N"

- Tính chất:

+ Nếu N = 1 thì N không là số nguyên tố

+ Nếu 1 < N < 4 thì N là số nguyên tố

2. Ý tưởng

- N<4: Xem như bài toán đã được giải quyết

- N≥4: Tìm ước i đầu tiên > 1 của N

+ Nếu i < N thì N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N)

+ Nếu i = N thì N là số nguyên tố

3. Xây dựng thuật toán

a) Cách liệt kê

Bước 1: Nhập số nguyên dương N

Bước 2: Nếu N=1 thì thông báo "N không là số nguyên tố", kết thúc;

Bước 3: Nếu N<4 thì thông báo "N là số nguyên tố", kết thúc;

Bước 4: i← 2;

Bước 5: Nếu i là ước của N thì đến bước 7

Bước 6: i← i+1 rồi quay lại bước 5; ( tăng i lên 1 đơn vị)

Bước 7: Nếu i = N thì thông báo "N là số nguyên tố", ngược lại thì thông báo "N không là số nguyên tố", kết thúc;


Hình 1. Sơ đồ khối thuật toán kiểm tra tính nguyên tố của một số nguyên dương N​

Lưu ý: Nếu N ≥ 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố