Nhận biết số nguyên tố và trả lời nhanh bằng sàng Eratosthenes

Lan cần chọn các thẻ mang số nguyên tố trong hộp có 50 thẻ đánh số từ 1 đến 50. Sau đó, Minh hỏi 20 lần số thẻ được chọn trong những đoạn khác nhau. Kiểm tra lại từng số cho mỗi câu hỏi sẽ lặp lại rất nhiều phép chia.

Một số nguyên tố có đúng hai ước dương

Một ước (divisor) của số nguyên n là số nguyên dương chia hết n. Chẳng hạn, 6 có bốn ước dương: 1, 2, 3 và 6. Một số nguyên tố (prime number) là số nguyên lớn hơn 1 và có đúng hai ước dương: 1 và chính nó.

Một hợp số (composite number) là số nguyên lớn hơn 1 nhưng không phải số nguyên tố. Số 1 chỉ có một ước dương, nên không thuộc hai nhóm trên. Các số không dương cũng không phải số nguyên tố theo định nghĩa này.

Chương trình dưới đây liệt kê ước của từng số nhỏ. Dữ liệu đã nằm trong danh sách values:

values = [1, 2, 6, 7]
for n in values:
    divisors = [d for d in range(1, n + 1) if n % d == 0]
    print(n, divisors)

1 [1]
2 [1, 2]
6 [1, 2, 3, 6]
7 [1, 7]

Số 2 và 7 có đúng hai ước; số 6 có bốn ước. Vì 1 chỉ có một ước, đừng coi điều kiện “không tìm thấy ước ở giữa” là đủ khi chưa kiểm tra n > 1.

Chỉ có một số nguyên tố chẵn là 2. Mọi số chẵn lớn hơn 2 đều có thêm ước 2. Tuy nhiên, số lẻ chưa chắc nguyên tố: 9 chia hết cho 3.

Thử ước đến căn bậc hai là đủ cho một số

Giả sử cần kiểm tra n = 36. Các cặp ước dương của nó là (1, 36), (2, 18), (3, 12), (4, 9) và (6, 6). Trong mỗi cặp, ít nhất một số không vượt quá 6, tức căn bậc hai của 36.

Căn bậc hai (square root) của n là số không âm mà bình phương bằng n. Không phải số nguyên nào cũng có căn là số nguyên. Để kiểm tra 29, bạn chỉ cần thử 2, 3, 4 và 5 vì 5 * 5 <= 29 còn 6 * 6 > 29.

Vì sao quy tắc này đúng? Nếu n = a * b mà cả a và b đều lớn hơn căn của n, tích của chúng sẽ lớn hơn n. Điều đó mâu thuẫn với a * b = n. Do đó, mỗi hợp số có một ước từ 2 đến căn của nó.

Ta có thể so sánh số nguyên d * d <= n để tránh tính căn bằng số thực. Đoạn sau đọc một số, kiểm tra rồi in YES hoặc NO:

29

n = int(input())
if n < 2:
    print("NO")
else:
    d = 2
    while d * d <= n and n % d != 0:
        d += 1
    print("YES" if d * d > n else "NO")

YES

Không số nào từ 2 đến 5 chia hết 29, nên chương trình trả YES. Nếu nhập 49, vòng lặp phải thử cả 7 vì 7 * 7 == 49. Dùng d * d < n sẽ bỏ sót đúng ước này.

Hàm sau gom quy tắc thành một chỗ. Nó cho phép tái sử dụng cùng cách kiểm tra với nhiều dữ liệu nhỏ:

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

for x in [-3, 0, 1, 2, 9, 11]:
    print(x, is_prime(x))

-3 False
0 False
1 False
2 True
9 False
11 True

Vòng lặp dừng ngay khi tìm thấy ước. Nếu không tìm thấy ước nào trước giới hạn, chứng minh cặp ước đảm bảo số đó là nguyên tố. Với n <= 10^9, số lượt thử tối đa khoảng 31622. Một vài truy vấn như vậy thường phù hợp, nhưng cần đo thời gian theo máy chấm thực tế.

Độ phức tạp thời gian (time complexity) mô tả cách lượng việc tăng theo kích thước dữ liệu. Ở đây, một lần kiểm tra cần O(√n) phép thử và O(1) bộ nhớ phụ. Với 10000 số gần 10^9, phép thử độc lập có thể lên tới khoảng 316 triệu lượt, nên cần xem xét phương pháp khác.

Bảng sàng giữ nguyên tố và loại bội của chúng

Nếu câu hỏi đều nằm trong khoảng từ 0 đến một giới hạn N vừa phải, bạn có thể chuẩn bị kết quả một lần. Sàng Eratosthenes (Sieve of Eratosthenes) dùng bảng đánh dấu để loại các hợp số.

Bắt đầu bằng cách coi các số từ 2 đến N là ứng viên. Khi gặp một ứng viên p còn được giữ, đánh dấu các bội của p từ p * p trở đi là hợp số. Sau khi xử lý các p có p * p <= N, những ứng viên còn lại là số nguyên tố.

Ô 0 và ô 1 không bao giờ là ứng viên vì không thỏa định nghĩa. Chúng xuất hiện trong hình để chỉ số trùng với giá trị trên thẻ. Dấu gạch ở hai ô này có nghĩa là đã loại từ lúc khởi tạo.

Hình sau mô tả sàng từ 2 đến 20. Dấu gạch chỉ những số đã bị loại; số chưa xét tiếp vẫn được giữ:

Với p = 3, số 6 đã bị 2 loại. Số 9 là bội đầu tiên chưa chắc được xử lý, vì 3 * 3 = 9. Tương tự, trước khi tới 5, các bội 10, 15 và 20 đều đã bị 2 hoặc 3 loại.

Xét bội p * k nhỏ hơn p * p: khi đó k < p. Số k có ít nhất một ước nguyên tố nhỏ hơn p. Sàng đã xử lý ước đó, nên p * k đã bị đánh dấu. Bắt đầu từ p * p tránh làm lại các bước đó mà không bỏ sót hợp số.

Mỗi hợp số x có một ước nguyên tố p <= √x <= √N. Khi sàng xử lý p, nó đánh dấu x. Ngược lại, sàng chỉ đánh dấu bội có ít nhất hai thừa số lớn hơn 1, nên không loại nguyên tố.

Đây là chương trình sàng trọn vẹn với N = 30. Các ô chỉ số 0 và 1 được đặt riêng vì cả hai không phải nguyên tố:

30

def sieve(n):
    prime = [True] * (n + 1)
    if n >= 0:
        prime[0] = False
    if n >= 1:
        prime[1] = False
    p = 2
    while p * p <= n:
        if prime[p]:
            for multiple in range(p * p, n + 1, p):
                prime[multiple] = False
        p += 1
    return prime

n = int(input())
prime = sieve(n)
print(*[x for x in range(n + 1) if prime[x]])

2 3 5 7 11 13 17 19 23 29

Dòng range(p * p, n + 1, p) có bước nhảy p và bao gồm n khi n là bội. Nếu thay n + 1 bằng n, hợp số ở đúng giới hạn có thể không được đánh dấu. Nếu N bằng 0 hoặc 1, bảng vẫn hợp lệ và danh sách kết quả rỗng.

Bảng sau được chương trình tạo từ chính dữ liệu 2 đến 20. Cột "Ước nhỏ nhất" cho biết ước đầu tiên được tìm thấy; dấu gạch nghĩa là không có ước giữa 1 và chính nó:

Bảng dò từng số cho thấy nguyên nhân một giá trị bị loại. Sàng đi theo chiều ngược lại: với mỗi ước nguyên tố, nó đánh dấu nhiều bội cùng lúc. Đây là hai cách tổ chức phép kiểm tra, không phải hai định nghĩa khác nhau.

Sàng cổ điển có độ phức tạp O(N log log N) và dùng O(N) ô nhớ. Mỗi nguyên tố p đóng góp nhiều nhất khoảng N / p lượt đánh dấu. Tổng các phần đó tăng chậm hơn N log N; tài liệu đọc thêm trình bày chứng minh đầy đủ.

Ví dụ N = 1000000 cần một triệu ô đánh dấu và chỉ phải xét các p tới 1000. Một list chứa tham chiếu nên tốn nhiều hơn một byte mỗi ô. Nếu bộ nhớ chặt, bytearray lưu từng cờ bằng một byte; vẫn cần tính cả các bảng bổ sung.

Bảng cộng dồn biến mỗi đoạn thành hai lần tra cứu

Lan đã biết thẻ nào là nguyên tố, nhưng Minh còn hỏi nhiều đoạn. Quét từ L đến R cho mỗi câu vẫn lặp việc khi các đoạn giao nhau. Ta chuẩn bị số lượng nguyên tố từ 0 đến từng vị trí.

Tổng tiền tố (prefix sum) tại x là tổng giá trị từ đầu đến x. Ở đây, đặt giá trị của số nguyên tố bằng 1 và các số khác bằng 0. Gọi count[x] là số nguyên tố không vượt quá x.

Với đoạn đóng [L, R], kết quả là count[R] - count[L - 1]. Phần bị trừ chứa đúng các số nhỏ hơn L, nên L và R đều được tính nếu là nguyên tố. Khi L = 0, không dùng count[-1]: hãy lấy phần trừ bằng 0.

Chương trình sau nhận giới hạn và một đoạn, sau đó tạo bảng đếm. Điều kiện đầu vào là 0 <= L <= R <= N:

20 4 13

n, left, right = map(int, input().split())
prime = [True] * (n + 1)
prime[0] = False
if n >= 1:
    prime[1] = False
p = 2
while p * p <= n:
    if prime[p]:
        for x in range(p * p, n + 1, p):
            prime[x] = False
    p += 1
count = [0] * (n + 1)
for x in range(1, n + 1):
    count[x] = count[x - 1] + int(prime[x])
before = count[left - 1] if left > 0 else 0
print(count[right] - before)

4

Các thẻ 5, 7, 11 và 13 đều nằm trong đoạn. Bảng tiền tố tại 13 chứa cả 2 và 3; phép trừ tiền tố tại 3 bỏ đúng hai số đó. Đổi left thành 0 thì phần cần trừ không có phần tử nào.

Đoạn sau chỉ kiểm tra hai đầu mút. Nó dùng danh sách nhỏ để làm rõ quy ước đoạn đóng:

flags = [False, False, True, True, False, True]
count = [0] * len(flags)
for i in range(1, len(flags)):
    count[i] = count[i - 1] + int(flags[i])
for left, right in [(0, 1), (2, 2), (4, 5)]:
    before = count[left - 1] if left else 0
    print(left, right, count[right] - before)

0 1 0
2 2 1
4 5 1

Đoạn [2, 2] có một nguyên tố dù hai đầu bằng nhau. Đoạn [0, 1] không có nguyên tố. Lấy count[R] - count[L] sẽ vô tình bỏ đầu trái khi L là nguyên tố.

Với N = 1000000 và 10000 câu hỏi, tiền xử lý cần O(N log log N) cho sàng và O(N) cho bảng đếm. Sau đó mỗi câu cần O(1) phép tra cứu. Quét tối đa một triệu số cho từng câu có thể đòi hỏi tới mười tỉ lượt xét.

Chọn phương pháp theo số truy vấn và miền giá trị

Không có một giới hạn duy nhất áp dụng cho mọi máy. Bạn cần xét cả số lượng truy vấn, miền số và bộ nhớ cho phép. Các tình huống sau cho thấy cách ước lượng trước khi viết code:

Nếu giới hạn số lên đến 10^12, một bảng có một nghìn tỉ ô không còn là lựa chọn thông thường. Một số đơn lẻ vẫn có thể thử đến một triệu ước, nhưng nhiều số như thế cần phân tích thêm. Đừng chọn sàng chỉ vì đề có từ “nguyên tố”.

Ví dụ sau tìm nguyên tố lớn nhất không vượt quá một giới hạn nhỏ. Sàng được xây một lần, rồi duyệt ngược để tìm ô còn giữ:

20

n = int(input())
prime = [True] * (n + 1)
prime[0] = False
if n >= 1:
    prime[1] = False
p = 2
while p * p <= n:
    if prime[p]:
        for x in range(p * p, n + 1, p):
            prime[x] = False
    p += 1
answer = -1
for x in range(n, 1, -1):
    if prime[x]:
        answer = x
        break
print(answer)

19

Giá trị -1 báo không tìm thấy khi giới hạn nhỏ hơn 2. Vì duyệt từ lớn xuống nhỏ, nguyên tố đầu tiên gặp được là đáp án lớn nhất. Sau sàng, vòng duyệt mất nhiều nhất N bước.

Một nhu cầu khác là đếm khoảng cách giữa hai nguyên tố liên tiếp trong một danh sách đã sàng. Khi duyệt tăng dần, chỉ cần nhớ nguyên tố ngay trước đó:

primes = [2, 3, 5, 7, 11, 13]
for i in range(1, len(primes)):
    print(primes[i - 1], primes[i], primes[i] - primes[i - 1])

2 3 1
3 5 2
5 7 2
7 11 4
11 13 2

Khoảng cách được tính giữa hai số liền nhau trong danh sách nguyên tố, không phải giữa hai vị trí bất kỳ. Nếu chỉ có một nguyên tố thì không có cặp nào. Quy ước kết quả cho trường hợp đó phải được nêu rõ trong từng đề.

Đọc điều kiện biên trước khi tin một kết quả

Một chương trình có thể chạy đúng với 29 nhưng sai ở 1, 2 hoặc 49. Mỗi giá trị đại diện cho một nhánh khác nhau. Danh sách sau giúp bạn kiểm tra bằng tay trước khi nộp:

• n < 2: hàm kiểm tra phải trả sai mà không thử chia.
• n = 2: không có ước cần thử nhưng kết quả là đúng.
• n = 49: cần xét ước 7 đúng tại ranh giới bình phương.
• N = 0 hoặc N = 1: sàng không được truy cập ô chưa tồn tại.
• L = R: đoạn có một số và vẫn tính hai đầu đóng.
• L = 0: phần tiền tố trước đoạn có giá trị 0.

Đoạn dưới đây so sánh hai cách độc lập trên các số nhỏ. Nếu xuất hiện một dòng khác nhau, hãy tìm số đầu tiên sai trước khi xét dữ liệu lớn:

def trial(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

limit = 50
flags = [True] * (limit + 1)
flags[0] = flags[1] = False
for p in range(2, limit + 1):
    if p * p > limit:
        break
    if flags[p]:
        for x in range(p * p, limit + 1, p):
            flags[x] = False
mismatches = [x for x in range(limit + 1) if flags[x] != trial(x)]
print(mismatches)

[]

Danh sách rỗng cho thấy hai cách trùng nhau trên miền được thử. Đây là bằng chứng hữu ích cho dữ liệu nhỏ, nhưng không thay thế chứng minh cho mọi đầu vào. Với dữ liệu lớn, bạn còn cần thử giới hạn thời gian và bộ nhớ thực tế.

Lỗi thường gặp

Tóm tắt

• Nguyên tố là số lớn hơn 1 có đúng hai ước dương; 0 và 1 không nguyên tố.
• Thử ước tới căn phù hợp cho một số; cần xét cả trường hợp bằng căn.
• Sàng đánh dấu từ bình phương của mỗi nguyên tố để chuẩn bị cả miền.
• Tiền tố đếm cho đoạn đóng bằng số lượng tới R trừ số lượng trước L.
• Chọn theo miền, số truy vấn, thời gian và bộ nhớ thay vì theo tên bài toán.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về math.isqrt giải thích căn bậc hai nguyên chính xác.
• Sàng Eratosthenes tại CP-Algorithms trình bày chứng minh và độ phức tạp.