埃氏筛法求素数

全称，埃拉托斯特尼筛法。

一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做素数；否则称为合数。

每个合数都可以写成几个质数相乘的形式，这几个质数就都叫做这个合数的质因数。

1. 试除法：O(√n)
2. Eratosthenes筛法: O(nlogn)
3. 欧拉筛：接近O(n)

#include <iostream>
using namespace std;
bool is_prime[100];

void init(){
    for(int i=2;i<100;++i)
    {
        is_prime[i]=1;
    }    
} 
void judge_prime(){
    init();
    for(int i = 2; i*i<100 ; ++i){
        if(is_prime[i]==1){
            for(int j = i*i ; j<100;j+=i){
                is_prime[j] = 0;
            }
        }
    } 
}
int main() {

    judge_prime();
    for(int i=2;i<100;++i)
    {
        if(i%10==0) {
            cout<<endl;
        }
        if(is_prime[i]==1)
        {
            cout<<i<<" ";
        }
    }
    cout<<endl;
    return 0;
}

​