Check Prime Number

Q: Độ phức tạp thời gian khi kiểm tra một số có phải là số nguyên tố không là bao nhiêu?

Phép chia thử đến √n cần thời gian O(√n) và không gian O(1) . Với n tối đa là 2^31-1 , số phép chia nhiều nhất vào khoảng 46,000 , hoặc 23,000 nếu bạn bỏ qua các ước số chẵn.

Q: 1 có phải là số nguyên tố không?

Không. Số nguyên tố có đúng hai ước khác nhau, 1 và chính nó, còn 1 chỉ có một ước. Việc loại 1 giúp phép phân tích mỗi số nguyên thành các thừa số nguyên tố luôn duy nhất.

Q: Có cách nào nhanh hơn để kiểm tra tính nguyên tố của các số rất lớn không?

Với một số 32-bit, phép chia thử (trial division) đến √n đủ nhanh. Với các số có hàng chục chữ số, chương trình dùng phép thử Miller-Rabin, kiểm tra một vài lũy thừa modulo thay vì thử các ước. Để liệt kê mọi số nguyên tố đến một giới hạn, Sàng Eratosthenes hiệu quả hơn việc kiểm tra từng số riêng lẻ.

Người mớiToán và mô phỏng

+10

Số nguyên tố là số nguyên lớn hơn 1 mà các ước duy nhất là 1 và chính nó. Bạn nhận được một số nguyên dương n. Trả về true nếu n là số nguyên tố, nếu không thì trả về false. Số 1 không phải là số nguyên tố.

Hàm

isPrime(n: integer) → boolean

ninteger: số nguyên dương cần kiểm tra
Trả vềboolean: true nếu n là số nguyên tố, false nếu không

Ràng buộc

1 ≤ n ≤ 2³¹ - 1

Ví dụ

Đầu vào: n = 29
Đầu ra: true
Giải thích: Không số nào trong 2, 3, 4 hay 5 chia hết 29, và 6 × 6 = 36 đã lớn hơn 29, nên không còn ước số nào cần tìm. 29 là số nguyên tố.

Đầu vào: n = 1
Đầu ra: false
Giải thích: Số nguyên tố có đúng hai ước số, 1 và chính nó. 1 chỉ có một ước số, nên đáp án là false.

Đầu vào: n = 91
Đầu ra: false
Giải thích: 91 có vẻ là số nguyên tố, nhưng 7 × 13 = 91. Ước số 7 xuất hiện trước khi quá trình tìm kiếm vượt qua √91 ≈ 9.5.

Câu hỏi mở rộng

Mọi số nguyên tố lớn hơn 3 đều có dạng 6k-1 hoặc 6k+1. Bạn có thể dùng điều đó để chỉ kiểm tra một phần ba số ước tiềm năng không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Thử mọi ước số từ 2 đến n-1 cần hơn hai tỷ phép chia với đầu vào là số nguyên tố lớn nhất. Các ước số tạo thành từng cặp có tích bằng n, và số nhỏ hơn trong mỗi cặp không vượt quá √n. Vì vậy, bạn chỉ cần tìm đến √n: nhiều nhất khoảng 23,000 số lẻ cần kiểm tra.

Thử mọi ước số

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Kiểm tra từng số d từ 2 đến n-1 với điều kiện n % d == 0 và trả về false ngay khi tìm thấy số chia hết. Đây là định nghĩa của số nguyên tố, vì vậy cách này đúng khi bạn trả về false với n < 2.

Số nguyên tố vượt qua mọi phép kiểm tra, nên vòng lặp chạy đến hết. Với n = 2147483647, là số nguyên tố, sẽ có khoảng 2.1 × 10^9 phép chia.

Thuật toán

Nếu n < 2, trả về false.
Lặp d từ 2 đến n-1.
Nếu n % d == 0, trả về false.
Sau vòng lặp, trả về true.

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

Thử chia đến căn bậc hai

Ý tưởng

Nếu d chia hết n, thì n / d cũng vậy. Cả hai không thể lớn hơn √n, nếu không tích của chúng sẽ lớn hơn n. Vì vậy, hợp số n luôn có một ước không lớn hơn √n: với 91, cặp ước là 7 và 13, và 7 ≤ 9.5. Nếu không có số nào từ 1 đến √n chia hết n, thì n là số nguyên tố.

Viết giới hạn dưới dạng d * d ≤ n, cách này chỉ dùng số nguyên và không cần làm tròn. Xử lý riêng 2, vì số chẵn n chỉ là số nguyên tố khi n bằng 2. Số lẻ n chỉ có các ước lẻ, vì vậy hãy bắt đầu từ 3 và tăng thêm 2 mỗi lần. Với n = 2147483647, vòng lặp chạy khoảng 23,000 lần.

Thuật toán

Nếu n < 2, trả về false.
Nếu n là số chẵn, trả về kết quả kiểm tra n == 2.
Bắt đầu với d bằng 3 và lặp khi d * d ≤ n, dùng kiểu 64 bit cho d.
Nếu n % d == 0, trả về false. Nếu không, cộng thêm 2 vào d.
Sau vòng lặp, trả về true.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Lỗi thường gặp và trường hợp biên

Trả về true cho 1. Số này chỉ có một ước, không phải hai, nên không phải số nguyên tố.
Loại bỏ 2 vì nó là số chẵn. Hãy kiểm tra n == 2 trước khi loại các số chẵn.
Lặp khi d * d < n thay vì ≤. Khi đó, bình phương của các số nguyên tố như 9 và 49 sẽ được xem là số nguyên tố.
Tràn số trong d * d. Với int 32 bit, 46341 × 46341 thành số âm, nên vòng lặp chạy quá xa √n. Hãy dùng kiểu 64 bit cho d, hoặc so sánh d ≤ n / d.

Câu hỏi thường gặp3

Độ phức tạp thời gian khi kiểm tra một số có phải là số nguyên tố không là bao nhiêu?

Phép chia thử đến √n cần thời gian O(√n) và không gian O(1). Với n tối đa là 2^31-1, số phép chia nhiều nhất vào khoảng 46,000, hoặc 23,000 nếu bạn bỏ qua các ước số chẵn.

1 có phải là số nguyên tố không?

Không. Số nguyên tố có đúng hai ước khác nhau, 1 và chính nó, còn 1 chỉ có một ước. Việc loại 1 giúp phép phân tích mỗi số nguyên thành các thừa số nguyên tố luôn duy nhất.

Có cách nào nhanh hơn để kiểm tra tính nguyên tố của các số rất lớn không?

Với một số 32-bit, phép chia thử (trial division) đến √n đủ nhanh. Với các số có hàng chục chữ số, chương trình dùng phép thử Miller-Rabin, kiểm tra một vài lũy thừa modulo thay vì thử các ước. Để liệt kê mọi số nguyên tố đến một giới hạn, Sàng Eratosthenes hiệu quả hơn việc kiểm tra từng số riêng lẻ.

def isPrime(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

n = 29

Đầu ra mong đợi

true