篩選法求素數，篩選法素數

篩選法求素數，篩選法素數

// 100 prime number
// 篩選法 即：“埃拉托色尼篩選法”
// 找出一個非素數就把它挖掉，最後剩下就是素數
/*
 * 找出1~n的素數表
 * 1、挖去1
 * 2、用下一個未挖去的數p去除p後面各數，把p的倍數挖掉
 * 3、檢查p是否小於n的整數部分（如果n=1000，則堅持p<31?），
 *    如果是，則返回（2）繼續執行，否則結束。
 * 4、剩下的就是素數了
 */
#include<iostream>
#include<iomanip>
using namespace std;
#include<cmath>
int main() {
	int i, j, n, a[101];
	for (i = 1; i <= 100; i++) {
		a[i] = i;
	}
	a[1] = 0;
	for (i = 2; i < sqrt(100); i++) {
		for (j = i + 1; j <= 100; j++) {
			if (a[i] != 0 && a[j] != 0) {
				if (a[j] % a[i] == 0) {
					a[j] = 0;
				}
			}
		}
	}
	cout<<endl;
	for (i = 1, n = 0; i <= 100; i++) {
		if (a[i] != 0){
			cout<<setw(5)<<a[i]<<" ";
			n++;
		}
		if (n == 10) {
			cout<<endl;
			n = 0;
		}
	}
    cout<<endl;
    return 0;
}