Một số bài toán và thuật toán liên quan tới số nguyên tố
Nguyễn Văn Trường
Trong các đề thi Olimpic tin học và trong nhiều bài toán tin chúng ta thường gặp dạng bài
tập có liên quan trực tiếp hay gián tiếp đến số nguyên tố. Các dạng bài tập này có thể là tìm
số nguyên tố thoả mãn một điều kiện nào đó hay kiểm tra tính nguyên tố của một số cho
trước. Bên cạnh đó, vấn đề tìm các số nguyên tố rất lớn đang được rất nhiều người quan
tâm vì sự ứng dụng thực tế của nó; đặc biệt là trong lĩnh vực mã hoá và an toàn thông tin,
việc tìm ra và sử dụng các số nguyên tố lớn đảm bảo tính an toàn rất cao cho hệ thống mã
hoá công khai nổi tiếng RSA. Bài viết này xin được giới thiệu với bạn đọc một số bài tập
và một số thuật toán hiệu quả có liên quan tới số nguyên tố. Trước hết chúng ta cùng
nghiên cứu một vài kiến thức làm cơ sở toán học cho các thuật toán sẽ trình bàỵ
Định nghĩa: Một số nguyên dương khác 1 được gọi là số nguyên tố nếu nó chỉ có hai ước
số dương là 1 và chính nó. Một số nguyên dương khác 1 không là số nguyên tố thì được
gọi là hợp số.
Định lý 1. Ước số dương bé nhất d khác 1 của một số nguyên dương a lớn hơn 1 là một số
nguyên tố.
Chứng minh Ta chứng minh bằng phản chứng như sau:
Giả sử d là hợp số => d = qd' , với 1 < q, d' < d. Mặt khác do a = dp theo giả thiết nên a =
qd'p => a có một ước số dương là d' với 1< d'< d. điều này là vô lý vì vậy d là số nguyên
tố.
Bài 1. Hãy phân tích một số nguyên n, n > 1 thành tích của các thừa số nguyên tố. Ví dụ
với n = 15 ta có dạng phân tích là n = 3.5
Theo định lý 1, ta có thể dễ dàng đưa ra thuật giải như sau:
B1.Tìm ước số dương d nhỏ nhất của n, (d >1) và gán n = n div d;
B2. Lặp lại B1 nếu n >1, ngược lại thì tập hợp các ước số đã tìm được chính là các thừa số
nguyên tố của n.
Định lý 2. Ước số dương bé nhất khác 1 của một hợp số a > 1 là một số nguyên tố không
vượt quá căn bậc hai của ạ
Định lý này cho phép ta kết luận: Một số nguyên dương n lớn hơn 1 là số nguyên tố nếu nó
không có ước số dương lớn hơn 1 và nhỏ hơn hoặc bằng
Chứng minh Giả sử p là ước số dương bé nhất khác 1 nhất của a =>p là số nguyên tố (Theo

= p
2
a
2
, 1≤ a
2
< a
1
.
Nếu a
2
= 1 => a
1
= p
2
=> a = p
1
p
2
.
Nếu a
2
> 1 => a
2
có ước nguyên tố là p
3
. Do đó a
2
= p
3


p
2
,...,p
n
xuất hiện theo thứ tự m
1
, m
2
,...,
m
n
lần thì ta có thể viết a dưới dạng:
và dạng này được gọi là dạng phân tích chính tắc hay dạng phân tích
tiêu chuẩn của ạ
Ví dụ 720 = 2
4
.3
2
.5
Bài 2. Cho trước số nguyên dương N, hãy tìm dạng phân tích chính tắc của N!=1.2.3...N.
Dữ liệu vào trong file văn bản NUM.INP trong đó chứa số nguyên dương N (2≤N≤ 10
000). Dữ liệu đưa ra file NUM.OUT bao gồm nhiều dòng, mỗi dòng gồm hai số ghi cách
nhau một dấu cách: số thứ nhất là thừa số nguyên tố của N và số thứ hai là số mũ tương
ứng.
Ví dụ:
NUM.INP
4
NUM.OUT
2 3

+
. Do đó n là
hợp số. Nếu n chia cho 6 dư 3 hoặc 4 thì ta cũng chứng minh được n là hợp số.
Định lý 5. Một số nguyên dương n là số nguyên tố nếu nó không chia hết cho bất kỳ số
nào trong dãy các số nguyên tố nhỏ hơn hoặc bằng .
Chứng minh Từ định lý 2 ta thấy rằng để chỉ ra n là số nguyên tố thì ta chỉ cần chứng tỏ
rằng nếu n không chia hết bất kỳ số nào trong dãy các số nguyên tố nhỏ hơn hoặc bằng
thì n cũng không chia hết cho bất kỳ số nào trong dãy các số nguyên nhỏ hơn hoặc bằng
. Thật vậy, giả sử n chia hết cho một hợp số m, m ≤ tức là n = mk, 1< m,k < n. Vì m
là hợp số nên tồn tại một ước nguyên tố d của m sao cho m = qd, 1< q,d < m => n = mk =
qdk, hay m chia hết cho một số nguyên tố d với d < m < n, điều này là mâu thuẫn với giả
thiết.
Sử dụng định lý này ta thấy rằng để kiểm tra một số nguyên n có phải là số nguyên tố hay
không ta chỉ cần kiểm tra n không chia hết cho bất kỳ số nào trong dãy các số nguyên tố
nhỏ hơn hay bằng
.
Từ hai định lý trên ta xây dựng một thuật toán tạm chấp nhận được để kiểm tra tính nguyên
tố của một số nguyên dương n thông qua một hàm như sau:
function isPrime(n:longint):boolean;
var i:longint;j:byte;
begin
isPrime:=true;
if n<2 then begin isPrime:=false;exit end;
if (n=2)or(n=3)then begin isPrime:=true; exit end;
if n mod 2=0 then begin isPrime:=false;exit end;
if n mod 3=0 then begin isPrime:=false;exit end;
i:=5;j:=2;
while i<=trunc(sqrt(n))do
begin
if n mod i =0 then begin isPrime:=false; exit end;

Bài 5. Cho trước một số nguyên dương N, 1< N< 500 000 hãy tìm giá trị của hàm π(n).
Bài 6. Cho trước một số nguyên dương N, 1< N< 10
18
hãy tìm một số nguyên tố M nhỏ
nhất và lớn hơn N. Ví dụ với N = 1000 thì M= 1009 với N = 10000000000000000 thì M =
10000000000000061.
Phân tích và hướng dẫn giải: thuật toán đưa ra rất đơn giản, tuy nhiên cần tìm ra thuật toán
hiệu quả để chạy trong thời gian chấp nhận được. Giải pháp đưa ra như sau:
Xuất phát từ N, tìm cách tăng N theo bước tăng 2, 4, 2, 4... Mỗi khi tăng N, kiểm tra xem N
có phải là số nguyên tố không bằng cách duyệt các ước số của N cũng theo bước tăng 2, 4,
2, 4... và các ước đó không vượt quá căn bậc hai của N.
Vấn đề là cần cài đặt các phép toán phù hợp để thoả mãn yêu cầu dữ liệu của đầu bài là N
có thể lớn tới 17 chữ số, M có thể lớn tới 18 chữ số. Như vậy, để làm được bài này ta cần
sử dụng cấu trúc dữ liệu là số thực và xây dựng tập hợp một vài phép toán như DIV (phép
chia lấy phần nguyên), MOD (phép chia lấy phần dư)... và ta gọi cấu trúc dữ liệu đó là số
giả nguyên. Khi có số giả nguyên thì ta có thể thao tác với các số nguyên lớn tới 20-21 chữ
số (bằng số chữ số có nghĩa của kiểu dữ liệu thực).
Thuật toán được minh hoạ qua chương trình sau:
{$N+,B-}
uses crt;
type bigInt=comp;
function DivB(a,b:bigint):bigint;
begin
DivB:=int(a/b);
{ham cho phan nguyen cua mot so thuc va
tra ve la kieu so thuc}
end;
function ModB(a,b:bigint):bigint;
begin
ModB:=a-b*int(a/b);