Sàng Eratosthenes trong Python & C++

Sàng Eratosthenes là gì?

Sàng Eratosthenes là phương pháp sàng số nguyên tố đơn giản nhất. Nó là một thuật toán số nguyên tố được sử dụng để tìm ra mọi số nguyên tố trong một giới hạn nhất định. Có một số phương pháp sàng số nguyên tố khác nhau, bao gồm Sàng Eratosthenes, Sàng Atkin và Sàng Sundaram.

Từ ngữngười hay nói“Sieve” đề cập đến một dụng cụ dùng để lọc các chất. Theo cùng một tinh thần, thuật toán sàng trong Python và các ngôn ngữ khác đề cập đến một phương pháp lọc ra các số nguyên tố từ một danh sách các số nguyên.

Thuật toán này lọc các số nguyên tố bằng phương pháp lặp. Quá trình lọc bắt đầu với số nguyên tố nhỏ nhất. Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có hai ước số, đó là 1 và chính nó. Numbers Những số không phải là số nguyên tố được gọi là số hợp số.

Tại sao lại sử dụng sàng Eratosthenes?

Trong phương pháp sàng Eratosthenes, trước tiên người ta chọn một số nguyên tố nhỏ, sau đó loại bỏ tất cả các bội số của nó. Quá trình này chạy lặp đi lặp lại trong một phạm vi nhất định, tạo ra mọi số nguyên tố đến n một cách hiệu quả mà không cần thực hiện phép chia thử trên từng số ứng viên.

Điều này làm cho thuật toán sàng nhanh hơn so với việc kiểm tra tính nguyên tố từng số một. Nó được sử dụng rộng rãi trong lý thuyết số, mật mã học, hàm băm và lập trình thi đấu, nơi cần tạo ra nhiều số nguyên tố một cách nhanh chóng.

Ví dụ:

Chúng ta hãy xét dãy số từ 2 đến 10.

Sau khi áp dụng phương pháp sàng Eratosthenes, ta sẽ thu được danh sách các số nguyên tố 2, 3, 5, 7.

Thuật toán sàng Eratosthenes

Đây là thuật toán sàng Eratosthenes:

Bước 1) Hãy lập danh sách các số từ 2 đến phạm vi n đã cho. Chúng ta bắt đầu với 2 vì nó là số nguyên tố nhỏ nhất và đầu tiên.

Bước 2) Chọn số nhỏ nhất trong danh sách, x (ban đầu x bằng 2), duyệt qua danh sách và lọc ra các số hợp số tương ứng bằng cách đánh dấu tất cả các bội số của số đã chọn.

Bước 3) Sau đó chọn số nguyên tố tiếp theo hoặc số nhỏ nhất chưa được đánh dấu trong danh sách và lặp lại bước 2.

Bước 4) Lặp lại bước trước đó cho đến khi giá trị của x nhỏ hơn hoặc bằng căn bậc hai của n (x<=).

Lưu ý: Lý luận toán học khá đơn giản. Dãy số n có thể được phân tích thành thừa số nguyên tố như sau:

n = a * b

Một lần nữa, n = *

= (hệ số nhỏ hơn ) * (hệ số lớn hơn )

Vì vậy ít nhất một trong số thừa số nguyên tố hoặc cả hai phải là <= Do đó, việc đi lên đến sẽ có đủ.

Bước 5) Sau bốn bước đó, các số chưa được đánh dấu còn lại sẽ là tất cả các số nguyên tố trong phạm vi n đã cho.

Ví dụ minh họa

Ví dụ:

Chúng ta hãy lấy một ví dụ và xem nó hoạt động như thế nào.

Trong ví dụ này, chúng ta sẽ tìm danh sách các số nguyên tố từ 2 đến 25. Vậy, n = 25.

Bước 1) Bước đầu tiên, chúng ta sẽ lấy một danh sách các số từ 2 đến 25 vì chúng ta đã chọn n = 25.

Bước 2) Tiếp theo, ta chọn số nhỏ nhất trong danh sách, là x. Ban đầu x = 2 vì nó là số nguyên tố nhỏ nhất. Sau đó, ta duyệt qua danh sách và đánh dấu các bội số của 2.

Các bội số của 2 ứng với giá trị n đã cho là: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Lưu ý: Màu xanh lam biểu thị số được chọn, và màu hồng biểu thị các bội số bị loại bỏ.

Bước 3) Sau đó, chúng ta chọn số không được đánh dấu nhỏ nhất tiếp theo là 3 và lặp lại bước cuối cùng bằng cách đánh dấu bội số của 3.

Bước 4) Chúng ta lặp lại bước 3 theo cách tương tự cho đến khi x = hoặc 5.

Bước 5) Các số còn lại không được đánh dấu là các số nguyên tố từ 2 đến 25.

giả-Code

Đoạn mã giả sau đây thể hiện cấu trúc cơ bản của thuật toán Sàng Eratosthenes trước khi chúng ta chuyển nó thành mã thực tế.

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Sàng Eratosthenes C/C++ Code Ví dụ

Dưới đây là bản đầy đủ. C++ Đây là bản triển khai thuật toán Sàng Eratosthenes, in ra mọi số nguyên tố đến một giới hạn trên được chọn.

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    }
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

Đầu ra:

2 3 5 7 11 13 17 19 23

Sàng Eratosthenes Python Ví dụ về chương trình

Sau đây Python Chương trình này thực hiện thuật toán tương tự bằng cách sử dụng danh sách boolean và vòng lặp while.

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Đầu ra:

2
3
5
7
11
13
17
19
23

Sàng phân đoạn

Chúng ta đã thấy rằng thuật toán sàng Eratosthenes chạy một vòng lặp qua toàn bộ phạm vi số. Do đó, nó cần không gian bộ nhớ O(n) để lưu trữ các số. Tình hình trở nên phức tạp khi chúng ta cố gắng tìm số nguyên tố trong một phạm vi rất lớn, bởi vì việc phân bổ một khối bộ nhớ lớn như vậy cho một n lớn hơn là không khả thi.

Thuật toán có thể được tối ưu hóa bằng cách giới thiệu một số tính năng mới. Ý tưởng là chia dãy số thành các phân đoạn nhỏ hơn và tính toán các số nguyên tố trong các phân đoạn đó từng cái một. Đây là một cách hiệu quả để giảm độ phức tạp của không gian. Phương pháp này được gọi là sàng phân đoạn.

Việc tối ưu hóa có thể đạt được theo cách sau:

1. Dùng sàng đơn giản để tìm các số nguyên tố từ 2 đến và lưu trữ chúng trong một mảng.
2. Chia phạm vi [0…n-1] thành nhiều đoạn có kích thước tối đa .
3. Với mỗi đoạn, hãy lặp qua đoạn đó và đánh dấu các bội số của các số nguyên tố tìm được ở bước 1. Bước này yêu cầu độ phức tạp O() ở mức tối đa.

Sàng thông thường yêu cầu không gian bộ nhớ phụ O(n), trong khi sàng phân đoạn yêu cầu O(n).), đây là một cải tiến đáng kể đối với n lớn. Phương pháp này cũng có một nhược điểm, đó là nó không cải thiện độ phức tạp về thời gian.

Phân tích độ phức tạp

Hiểu rõ cả độ phức tạp về không gian và thời gian sẽ giúp bạn lựa chọn giữa thuật toán sàng thông thường và thuật toán sàng phân đoạn cho một kích thước bài toán nhất định.

Không gian phức tạp:

Thuật toán sàng Eratosthenes đơn giản yêu cầu không gian bộ nhớ O(n). Sàng phân đoạn yêu cầu O(n).) không gian phụ.

Độ phức tạp về thời gian:

Độ phức tạp thời gian của thuật toán Sàng Eratosthenes thông thường là O(n*log(log(n))). Lý do đằng sau độ phức tạp này được thảo luận bên dưới.

Với một số n cho trước, thời gian cần thiết để đánh dấu một số hợp số (tức là một số không phải số nguyên tố) là hằng số. Do đó, số lần vòng lặp chạy bằng:

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

Dãy số điều hòa của tổng các số nguyên tố có thể được suy ra là log(log(n)):

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Vì vậy, độ phức tạp về thời gian sẽ là:

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

Do đó, độ phức tạp thời gian là O(n * log(log(n))).

Tiếp theo, bạn sẽ tìm hiểu về Tam giác Pascal.

Câu Hỏi Thường Gặp