Thuật toán sàng nguyên tố(Eratosthenes) trong C++

• • Thuật toán sàng nguyên tố Eratosthenes là một trong những cách hiệu quả nhất để tìm tất cả các số nguyên tố nhỏ hơn n khi n nhỏ hơn 1 triệu phần tử.
  • Ví dụ:
  • Input:
  • Số nguyên n ( 0 ≤ n ≤ 10⁶ ).
  • Output
  • In ra trên một dòng các sốnguyên tố không vượt quá n, mỗi số cách nhau một khoảng trắng.
    

    Input	Output
    4	2 3
    11	2 3 5 7 11

  • Thuật toán:
  • Ví dụ ta muốn sàng các nguyên tố trong đoạn từ 0 đến 20 thì ta khai báo mảng b[21] và b[i] = 1 cho tất cả các giá trị từ 0 đến 20 đều là số nguyên tố.
  • Loại bỏ thủ công b[0] = 0, b[1] = 1. Vì 0 và 1 không phải là số nguyên tố.
  • Sau đó ta duyệt từ 2 đến \sqrt{20}. Khi duyệt đầu tiên từ 2 và 2 là số nguyên tố, tiếp tục duyệt các bội của 2 và đánh dấu các bội đó là không phải số nguyên tố.
  • Duyệt tiếp theo số 3 là số nguyên tố, duyệt các bội của 3 và đánh dấu các bội đó là không phải số nguyên tố. Lưu ý chỉ cần đánh dấu bội đầu tiên i*i (9), các bội còn lại ta cộng cho 3.
  • Còn lại duyệt từ 2 đến 20, các số nào có giá trị b[i] = 1 thì là số nguyên tố
  • Code C++:

 
#include<bits/stdc++.h>
using namespace std;
int b[1000001];

bool sangnguyento() {
    for(int i = 0; i <= 1000001; i++) 
        b[i] = 1;//coi tất cả các số từ 0 đến n là số nguyên tố
        b[0] = b[1] =0; //loại bỏ số 0 và 1
        for(int i = 2; i <= 1000; i++) { 
        	if(b[i]){ //nếu i là số nguyên tố
        		for(int j=i*i; j <= 1000000; j+=i) { //duyệt các bội của i và cho nó là không phải số nguyên tố
        			b[j]=0; // j không còn là số nguyên tố
        			
        	    }
			} 	
    }   
}
int main(){
	sangnguyento();
 	int n;
	cin>>n;
	for(int i=0;i<=n; i++){ 
		if (b[i])
		cout << i << " ";
	}
	return 0;
}

– Kết quả: