Đề bài: Kiểm tra một số A có phải là số nguyên tố hay không. Một số được gọi là số nguyên tố khi nó chỉ có 2 ước duy nhất là 1 và chính nó, nói cách khác, số nguyên tố là số chỉ chia hết cho chính nó và 1.
Số 2 là số nguyên tố nhỏ nhất, nó chỉ chia hết cho chính nó và 1.
Input: Mỗi hàng sẽ chứa một số nguyên N (1 <= N <= 10^12). Chương trình sẽ kết thúc khi gặp một ký tự không phải số nguyên.
Output: YES nếu N là số nguyên tố, ngược lại in NO.
Phân tích:
Trước hết, cận trên của N là 10^12. Nếu dùng Sàng Eratosthenes bình thường, ta phải tạo một mảng 10^12 phần tử rồi lưu giá trị của từng phần tử. Nếu dùng phương pháp ngây thơ (dumb algorithm to find prime numbers), duyệt từ 2 đến sqrt(N) thì trong trường hợp xấu nhất ta chỉ phải duyệt đến sqrt(10^12). Rõ ràng độ phức tạp về thời gian của Sàng Eratosthenes hơn hẳn phương pháp ngây thơ, tuy nhiên trong trường hợp này chúng ta cần một giải thuật hiệu quả hơn hẳn cả về không gian lẫn thời gian. Sàng Eratosthenes chiếm quá nhiều không gian, do vậy triển khai phương pháp ngây thơ sẽ có hiệu quả hơn.
Với những bài toán liên quan đến số nguyên tố, chúng ta chỉ áp dụng sàng Eratosthenes với những bài toán cần kiểm tra tính nguyên tố của nhiều số khác nhau, nhằm giải quyết 1 vấn đề lớn hơn (ex: tìm các số nguyên tố mà tổng của chúng bằng một số nguyên tố khác). Việc lạm dụng sàng Eratosthenes có thể dẫn đến việc chương trình của bạn hiệu quả trong việc truy xuất nhưng lãng phí thời gian trong quá trình khởi tạo bảng nguyên tố.
Code:
*Dùng Sàng Eratosthenes: O(Nlog(logN)) cho việc khởi tạo, O(1) cho việc truy xuất.
*Dùng phương pháp "ngây thơ": O(sqrt(N)) cho toàn bộ quá trình.
Bài viết có tham khảo lời giải của anh Phạm Văn Lâm cho bài PRIME1 (SPOJ). Điểm chung của cả 2 bài này là dùng để kiểm tra số nguyên tố trong phạm vi rất lớn. Bạn đọc có thể tham khảo đề PRIME1 tương tự.
Trước hết, cận trên của N là 10^12. Nếu dùng Sàng Eratosthenes bình thường, ta phải tạo một mảng 10^12 phần tử rồi lưu giá trị của từng phần tử. Nếu dùng phương pháp ngây thơ (dumb algorithm to find prime numbers), duyệt từ 2 đến sqrt(N) thì trong trường hợp xấu nhất ta chỉ phải duyệt đến sqrt(10^12). Rõ ràng độ phức tạp về thời gian của Sàng Eratosthenes hơn hẳn phương pháp ngây thơ, tuy nhiên trong trường hợp này chúng ta cần một giải thuật hiệu quả hơn hẳn cả về không gian lẫn thời gian. Sàng Eratosthenes chiếm quá nhiều không gian, do vậy triển khai phương pháp ngây thơ sẽ có hiệu quả hơn.
Với những bài toán liên quan đến số nguyên tố, chúng ta chỉ áp dụng sàng Eratosthenes với những bài toán cần kiểm tra tính nguyên tố của nhiều số khác nhau, nhằm giải quyết 1 vấn đề lớn hơn (ex: tìm các số nguyên tố mà tổng của chúng bằng một số nguyên tố khác). Việc lạm dụng sàng Eratosthenes có thể dẫn đến việc chương trình của bạn hiệu quả trong việc truy xuất nhưng lãng phí thời gian trong quá trình khởi tạo bảng nguyên tố.
Code:
*Dùng Sàng Eratosthenes: O(Nlog(logN)) cho việc khởi tạo, O(1) cho việc truy xuất.
*Dùng phương pháp "ngây thơ": O(sqrt(N)) cho toàn bộ quá trình.
Bài viết có tham khảo lời giải của anh Phạm Văn Lâm cho bài PRIME1 (SPOJ). Điểm chung của cả 2 bài này là dùng để kiểm tra số nguyên tố trong phạm vi rất lớn. Bạn đọc có thể tham khảo đề PRIME1 tương tự.
No comments:
Post a Comment