[Algo] Sieve of Eratosthenes

1.  Sieve of Eratosthenes
Sieve of Eratosthenes là một giải thuật tìm số nguyên tố rất phổ biến ở nước ngoài (ở VN thì tớ không biết).

Độ phức tạp: xem ở [1].

Tư tưởng của thuật toán:
Giả sử ta kiểm tra các số từ 1-100 xem có những số nào là nguyên tố.
Bắt đầu từ 2: ta lần lượt loại các bội của 2 ra khỏi danh sách (không tính 2, như vậy loại ra 4 6 8 10 ...
tiếp theo : loại các bội của 3 (6 9 12 ...)
...
cho đến hết.

Dễ dàng hiểu rằng ta đã loại đi các bội số(hợp số) và sau khi loại hết các số này thì chỉ còn lại các số nguyên tố.

Thuật toán cài đặt bằng Python2.7:


 https://github.com/hvnsweeting/FAMILUG/blob/master/Python/bulb_state.py

2. Số chính phương.


Có nét giống SoE, 1 thuật toán kiểm tra số chính phương  dựa vào tính chất đặc biệt của nó: các số chính phương có số ước không tầm thường là một số lẻ!

(mặc dù bạn hòan tòan có thể tìm số chính phương bằng cách tương tự như EoS nhưng thay vì loại các bội số của k thì ta chọn bình phương của k)

VD: 4 (2 * 2) có ước duy nhất là 2, 9 (3 * 3) có ước duy nhất là 3, 25 (5 * 5) có  ước duy nhất là 5. 25^2 có các ước là 5, 5^2, 5^3

Như vậy bài toán kiểm tra số chính phương đã chuyển thành bài toán kiểm tra xem số ước của 1 số có là lẻ không?
Thế nhưng khi ra đề, người ta có thể đắp lên phần xương bài toán những miếng thịt ngọt và ngon =p~ để che mắt thiên hạ như sau :D

Cho 100 cái bóng đèn đều đang tắt
người thứ nhất vào bật 100 bóng lên
người thứ 2 tắt các bóng 2 4 6 8 ...
người thứ 3 thay đổi trạng thái bóng 3 6 9...
người thứ 4 thay đổi trạng thái bóng 4 8 12 ...
...
người thứ 100 thay đổi trạng thái bóng thứ 100

Tìm các bóng đang bật?

Sau khi đọc đề, bạn có thể đưa ra nhận xét: 1 bóng đèn có trạng thái cuối cùng là bật nếu nó bị thay đổi trạng thái lẻ lần.

Thuật toán cài đặt bằng Python2.7:
https://github.com/hvnsweeting/FAMILUG/blob/master/Python/eratosthenes.py



[1] http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes