Tìm hiểu về Sàng nguyên tố mở rộng
Thuật toán sàng nguyên tố mở rộng (hay còn được gọi là Sàng nguyên tố trên mạng lưới) là một thuật toán để tìm tất cả các số nguyên tố từ 2 đến một giá trị nguyên dương n lớn hơn. Thuật toán này là một phiên bản mở rộng của thuật toán sàng nguyên tố cổ điển, được sử dụng để tìm tất cả các số nguyên tố từ 2 đến một giá trị n nhỏ hơn.
Thuật toán sàng nguyên tố mở rộng hoạt động bằng cách chia đều khoảng từ 2 đến n thành các phân đoạn bằng nhau. Sau đó, mỗi phân đoạn được xử lý độc lập bằng cách sử dụng một phiên bản cải tiến của thuật toán sàng nguyên tố cổ điển. Cụ thể, mỗi phân đoạn được chia thành các khoảng con có độ dài bằng nhau, sau đó áp dụng thuật toán sàng nguyên tố để loại bỏ các bội số của các số nguyên tố trong khoảng này. Kết quả là, tất cả các số nguyên tố trong khoảng này được tìm thấy.
Sau đó, các kết quả từ các phân đoạn được kết hợp lại để tìm tất cả các số nguyên tố từ 2 đến n. Tuy nhiên, việc kết hợp các kết quả này không hoàn toàn đơn giản do sự xuất hiện của các số nguyên tố trên biên giới của các phân đoạn. Để giải quyết vấn đề này, ta cần thực hiện một số thao tác bổ sung sau khi thuật toán đã hoàn tất.
Thuật toán sàng nguyên tố mở rộng có độ phức tạp thời gian là O(n log log n), cho phép tìm tất cả các số nguyên tố từ 2 đến một giá trị n lớn hơn một cách hiệu quả.
cài đặt thuật toán sàng nguyên tố mở rộng với Python
Để cài đặt thuật toán sàng nguyên tố mở rộng bằng Python, chúng ta có thể sử dụng thuật toán sàng nguyên tố Eratosthenes cải tiến. Dưới đây là một ví dụ về cách triển khai thuật toán này bằng Python:
def sieve_of_eratosthenes(n):
# Tạo một danh sách các số từ 0 đến n và đánh dấu tất cả các số là nguyên tố
primes = [True] * (n+1)
# Loại bỏ số 0 và 1 khỏi danh sách
primes[0], primes[1] = False, False
# Chạy vòng lặp từ 2 đến căn bậc hai của n
for i in range(2, int(n**0.5)+1):
# Nếu số i là số nguyên tố
if primes[i]:
# Loại bỏ tất cả các bội số của i trong phạm vi từ i^2 đến n
for j in range(i**2, n+1, i):
primes[j] = False
# Tạo danh sách chứa tất cả các số nguyên tố từ 2 đến n
prime_list = [i for i in range(2, n+1) if primes[i]]
return prime_list
Hàm sieve_of_eratosthenes(n) trả về một danh sách chứa tất cả các số nguyên tố từ 2 đến giá trị n. Chúng ta sử dụng một danh sách primes để đánh dấu tất cả các số là nguyên tố ban đầu, sau đó loại bỏ tất cả các bội số của các số nguyên tố trong danh sách này. Cuối cùng, chúng ta tạo danh sách prime_list chứa tất cả các số nguyên tố được tìm thấy.
Ví dụ sử dụng:
n = 100
primes = sieve_of_eratosthenes(n)
print(primes)
Cài đặt thuật toán sàng nguyên tố mở rộng với C++
Để cài đặt thuật toán sàng nguyên tố mở rộng bằng C++, chúng ta có thể sử dụng thuật toán sàng nguyên tố Eratosthenes cải tiến. Dưới đây là một ví dụ về cách triển khai thuật toán này bằng C++:
#include <iostream>
#include <vector>
using namespace std;
vector<int> sieve_of_eratosthenes(int n) {
// Tạo một vector các số từ 0 đến n và đánh dấu tất cả các số là nguyên tố
vector<bool> primes(n+1, true);
// Loại bỏ số 0 và 1 khỏi danh sách
primes[0] = false;
primes[1] = false;
// Chạy vòng lặp từ 2 đến căn bậc hai của n
for (int i = 2; i*i <= n; i++) {
// Nếu số i là số nguyên tố
if (primes[i]) {
// Loại bỏ tất cả các bội số của i trong phạm vi từ i^2 đến n
for (int j = i*i; j <= n; j += i) {
primes[j] = false;
}
}
}
// Tạo vector chứa tất cả các số nguyên tố từ 2 đến n
vector<int> prime_list;
for (int i = 2; i <= n; i++) {
if (primes[i]) {
prime_list.push_back(i);
}
}
return prime_list;
}
int main() {
int n = 100;
vector<int> primes = sieve_of_eratosthenes(n);
for (int prime : primes) {
cout << prime << " ";
}
cout << endl;
return 0;
}
Hàm sieve_of_eratosthenes(n) trả về một vector chứa tất cả các số nguyên tố từ 2 đến giá trị n. Chúng ta sử dụng một vector primes để đánh dấu tất cả các số là nguyên tố ban đầu, sau đó loại bỏ tất cả các bội số của các số nguyên tố trong vector này. Cuối cùng, chúng ta tạo vector prime_list chứa tất cả các số nguyên tố được tìm thấy.
Trong hàm main(), chúng ta tìm tất cả các số nguyên tố từ 2 đến 100 bằng cách gọi hàm sieve_of_eratosthenes(n) và lưu kết quả vào vector primes. Sau đó, chúng ta in ra tất cả các số nguyên tố này ra màn hình.