Thuật toán sàng Eratosthenes: Python, C++ Ví dụ

Sàng Eratosthenes là sàng số nguyên tố đơn giản nhất. Đây là thuật toán số nguyên tố để tìm kiếm tất cả các số nguyên tố trong một giới hạn nhất định. Có một số sàng số nguyên tố. Ví dụ: Sàng Eratosthenes, Sàng Atkin, Sàng Sundaram, v.v.

Từ ngữngười hay nói” có nghĩa là dụng cụ lọc chất. Như vậy, thuật toán sàng trong Python và các ngôn ngữ khác đề cập đến một thuật toán để lọc ra các số nguyên tố.

Thuật toán này lọc ra số nguyên tố theo cách tiếp cận lặp lại. 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 và chỉ có hai ước số, tức là 1 và chính số đó. Các số không phải là số nguyên tố được gọi là hợp số.

Trong sàng của phương pháp Eratosthenes, một số nguyên tố nhỏ được chọn trước tiên và tất cả các bội số của nó sẽ được lọc ra. Quá trình chạy trên một vòng lặp trong một phạm vi nhất định.

Ví dụ:

Hãy lấy phạm vi số từ 2 đến 10.

Sau khi áp dụng Sàng Eratosthenes sẽ ra 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) Tạo danh sách các số từ 2 đến phạm vi n đã cho. Chúng ta bắt đầu với số 2 vì đây 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 các số tổng hợp tương ứng bằng cách đánh dấu tất cả bội số của các 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 phải 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. Phạm vi số n có thể được phân tích thành hệ số-

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à <=. Như vậy, đi ngang qua sẽ có đủ.

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

Ví dụ:

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ì vậy, n=25.

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

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

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

Lưu ý: Màu xanh biểu thị số đã chọn và màu hồng biểu thị bội số bị loại

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ố không được đánh dấu còn lại sẽ là các số nguyên tố từ 2 đến 25.

Mã giả

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++ mã Ví dụ

#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

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:

Sàng phân đoạn

Chúng ta đã thấy rằng cần phải có Sàng Eratosthenes để thực hiện một vòng lặp qua toàn bộ dãy số. Vì vậy, nó cần dung lượng bộ nhớ O(n) để lưu trữ các số. Tình huống trở nên phức tạp khi chúng ta cố gắng tìm các số nguyên tố trong một phạm vi rất lớn. Việc phân bổ không gian bộ nhớ lớn như vậy cho 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:

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.
Chia phạm vi [0…n-1] thành nhiều đoạn có kích thước tối đa
Đối với mỗi phân đoạn, hãy lặp qua phân đoạn đó và đánh dấu bội số nguyên tố tìm thấy ở bước 1. Bước này yêu cầu 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 lớn đối với n lớn. Phương pháp này cũng có nhược điểm là không cải thiện được độ phức tạp về thời gian.

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

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). Và sàng phân đoạn yêu cầu
O() 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 dưới đây.

Với một số n cho trước, thời gian cần thiết để đánh dấu một hợp số (tức là các số không phải số nguyên tố) là không đổi. Vì vậy, 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 +…….∞)

Sự tiến triển hài hòa của tổng các số nguyên tố có thể được khấu trừ dưới dạng 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 O(n * log(log(n)))

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

Tổng kết

Sàng Eratosthenes lọc ra các số nguyên tố ở giới hạn trên nhất định.
Lọc một số nguyên tố bắt đầu từ số nguyên tố nhỏ nhất, “2”. Điều này được thực hiện lặp đi lặp lại.
Phép lặp được thực hiện đến căn bậc hai của n, trong đó n là phạm vi số đã cho.
Sau những lần lặp này, các số còn lại là số nguyên tố.

Bạn có thể thích: