thuật toán sang nguyên tố tối ưu là gì

Question

➻❥﹏๖ۣۜⓀⓔⓜ﹏๖ۣۜ · Accepted Answer

Sàng nguyên tố Eratosthenes (Sieve of Eratosthenes) là thuật toán tối ưu nhất và phổ biến nhất để tìm tất cả các số nguyên tố trong khoảng từ 1 đến $N$. Thuật toán này hoạt động bằng cách lập bảng và loại bỏ (sàng) dần các hợp số ra khỏi danh sách.

Timi · Answer

Thuật toán sàng nguyên tố tối ưu (hay còn gọi là Sieve of Eratosthenes) là một phương pháp hiệu quả để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương n. Thuật toán này hoạt động bằng cách loại bỏ các bội số của các số nguyên tố bắt đầu từ số 2. Dưới đây là cách hoạt động của thuật toán:

1. Tạo một danh sách các số từ 2 đến n.
2. Bắt đầu với số nguyên tố đầu tiên là 2. Đánh dấu tất cả các bội số của 2 (như 4, 6, 8,...) là không phải nguyên tố.
3. Tiếp tục với số nguyên tố tiếp theo (3) và đánh dấu tất cả các bội số của 3.
4. Lặp lại quá trình này cho đến khi bạn đã kiểm tra tất cả các số lên đến √n.
5. Các số còn lại không bị đánh dấu trong danh sách sẽ là các số nguyên tố.

Thuật toán này có độ phức tạp thời gian là O(n log log n), rất hiệu quả cho việc tìm số nguyên tố trong khoảng lớn.

Joy · Answer

{"userId":5436195,"userName":"Nguyễn Văn Huy"}

Sàng nguyên tố tối ưu (Sàng Eratosthenes) là thuật toán tìm tất cả các số nguyên tố trong khoảng từ $1$ đến $N$.

Cách hoạt động:

$$-$$Khởi tạo mảng đánh dấu các số là nguyên tố.Lặp từ $2$ đến $\sqrt{N}$.

$$-$$Với mỗi số nguyên tố, đánh dấu mọi bội số của nó là hợp số. Các số còn lại chính là số nguyên tố.

Quỳnh Anh · Answer

{"userId":5436195,"userName":"Nguyễn Văn Huy"}

Thuật toán sàng số nguyên tố tối ưu nhất hiện nay là Sàng Atkin (Sieve of Atkin), có độ phức tạp thời gian là $O(N / \log \log N)$.

Tuy nhiên, trong chương trình Tin học phổ thông, Sàng Eratosthenes (Sieve of Eratosthenes) là thuật toán tối ưu, phổ biến và dễ cài đặt nhất với độ phức tạp $O(N \log \log N)$.

Dưới đây là chi tiết về hai thuật toán này kèm mã nguồn minh họa bằng Python và C++.

________________________________________

1. Sàng Atkin (Tối ưu nhất về lý thuyết)

Thuật toán này thay thế các phép chia của Eratosthenes bằng cách giải các phương trình bậc hai nồng cốt nhằm xác định tính nguyên tố của một số.

• Độ phức tạp thời gian: $O(N / \log \log N)$

• Độ phức tạp không gian: $O(N^{1/2 + o(1)})$

________________________________________

2. Sàng Eratosthenes cải tiến (Thực tế và Phổ biến)

Ý tưởng cốt lõi là loại bỏ tất cả các bội số của một số nguyên tố. Để tối ưu hóa hiệu năng, thuật toán chỉ cần duyệt đến $\sqrt{N}$ và bắt đầu sàng các bội số từ $i \times i$.

Mã nguồn Python (Sàng Eratosthenes)

python

def sieve_of_eratosthenes(n):

prime = [True] * (n + 1)

prime[0] = prime[1] = False

p = 2

while (p * p <= n):

if prime[p] == True:

# Cập nhật tất cả các bội số của p từ p*p trở đi

for i in range(p * p, n + 1, p):

prime[i] = False

p += 1

# Xuất ra danh sách các số nguyên tố

return [i for i in range(2, n + 1) if prime[i]]

# Ví dụ tìm số nguyên tố nhỏ hơn hoặc bằng 30

print(sieve_of_eratosthenes(30))

Use code with caution.

Mã nguồn C++ (Sàng Eratosthenes)

cpp

#include <iostream>

#include <vector>

using namespace std;

void sieveOfEratosthenes(int n) {

vector<bool> is_prime(n + 1, true);

is_prime[0] = is_prime[1] = false;

for (int p = 2; p * p <= n; p++) {

if (is_prime[p] == true) {

// Tối ưu: chạy từ p*p thay vì p*2

for (int i = p * p; i <= n; i += p)

is_prime[i] = false;

}

// In kết quả

for (int p = 2; p <= n; p++)

if (is_prime[p])

cout << p << " ";

}

int main() {

int n = 30;

sieveOfEratosthenes(n);

return 0;

}