Sàn lọc số nguyên tố

Toàn bộ số tự nhiên được chia làm ba loại: Loại 1 là các số nguyên tố ( như 2,3,5,7,11,13,…), Loại 2 là các hợp số ( 4,6,8,9,10,…) . Số “1″ không phải là số nguyên tố, cũng không phải là hợp số nên nó là một loại riêng thứ 3. Số nguyên tố là những số chỉ chia hết cho 1 và chính nó, còn hợp số có thể chia hết cho những số khác.
Trong một số bài toán yêu cầu cần xác định một số có phải là số nguyên tố không! Ví dụ như bài toán tìm thừa số nguyên tố của 1 dãy n số tự nhiên cho trước chẳng hạn. giả sử n=10, các số trong dãy là 17, 56, 45, 78, 12876, 998756, 1967, 567,1299907767, 34435343.
Cách thông thường là tại mỗi số, cho vòng lặp i chạy từ 2 đến căn bậc 2 của số đó rồi kiểm tra xem i có phải là số nguyên tố hay không bằng 1 vòng lặp khác nữa. Như vậy rất mất thời gian.
Có một cách nhanh hơn. Trước tiên chúng ta sẽ tạo ra một sàn nguyên tố ngay từ đầu. Khi cần xác định 1 số có phải là nguyên tố hay không chỉ cần 1 bước so sánh thôi.

Sàn nguyên tố thực ra là 1 mảng nguyento kiểu bool. Đầu tiên cho tất cả các phần tử có giá trị true.
Sau đó, chúng ta sẽ đánh dấu mảng tại vị trí những số nào không là số nguyên tố thành false. Những vị trí còn giá trị true thì sẽ là số nguyên tố.
Khi cần so sánh 1 số r có phải là nguyên tố hay không, chúng ta chỉ cần gọi (nguyento[r]==true).

Code demo:

Code:

//gia su trong bai nay minh hci xet den 1000
bool nguyento[1000];
for (int i=0;i<1000;i++) nguyento[i]=true;

nguyento[0]=nguyento[1]=false; //0 va 1 khong la so nguyen to

for (int i=2;i<sqrt(1000);i++)
    for (int j=2;j*i<1000;j++)
          nguyento[i*j]=false;

Đíng là cách của mình dùng trong trường hợp kiểm tra 1 số không nhanh hơn bình thường.
Nhưng mình đã có nói ngay từ đầu, trong trường hợp kiểm tra 1 chuỗi nhiều số để tìm ra những số nguyên tố chẳng hạn thì tố độ sẽ nahnh gấp rất nhiều lần.
Thay vì với mỗi phần tử bạn phải chạy sqrt (n) lần để kiểm tra phần tử n đó có phải là nguyên tố hay không theo cách thường thì lúc này bạn chỉ cần chạy 1 lần và sau đó kiểm tra từng phần tử chỉ bằng 1 phép so sánh. Chuỗi càng nhiều phần tử thì cách này lại cảng tỏ ra có hiệu quả. Những đề thi lập trình không bao giờ yêu cầu kiểm tra 1 phần tử mà rất nhiều phần tử, có khi đến hàng triệu!

Với lại mình xin đính chính lại, thuật toán đó không đến nỗi O(n^2) đâu. Cách tính độ phức tạp như thế nào thì mình không nhớ rõ nhưng 2 vong lặp đó không thể nào là O(n^2) được!

hi...Cái tính độ phức tạp vừa mới học...quá tính sơ sơ ban đầu thì hình như kết quả là tổng (1000/i - 2) i chạy từ 2 đến căn bật 2 của n....
(tại không bt vẽ cái sít ma lên trên này...