素数筛

#include<iostream>
#include<cstring>
#include<cmath>
#include <Windows.h>
using namespace std;
const int maxn=100000000;
bool a[maxn];
int prime[maxn];
int cnt = 0;

void prime2()//欧拉筛法
{
    memset(a, 0, sizeof(a));
    cnt = 0;
    // 使用的原理是算术基本定理，又称为正整数的唯一分解定理，即：每个大于 1 的自然数，要么本身就是质数，，要么可以写为 2 个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。
    for (int i = 2; i <= sqrt(maxn); i++)
    {
        if (!a[i])//如果你是一个素数把你加入到素数数组
            prime[cnt++] = i;
        // 下面这个循环每次都会循环不管i是素数还是合数
        for (int j = 0; j < cnt; j++)//以已经有的素数作为因子与该数相乘消除一部分合数
        {
            if (i*prime[j] > maxn)
                break; // 过大的时候跳出
            a[i*prime[j]] = 1;//将合数置一
            // 如果i是一个合数，而且i % prime[j] == 0，
            //可知以i为基础的合数在优化prime[j]时已经优化过了 ，那么就跳出
            if ((i%prime[j]) == 0)
                break;
        }
    }
}
int main()
{
    int n=100;
    //cin>>n;
    SYSTEMTIME t1,t2;
    GetLocalTime(&t1);
    prime2();
    for(int i=0;i<cnt;i++)
    {
        cout<<prime[i]<<" ";
    }
    GetLocalTime(&t2);
    cout<<"cost "<<t2.wSecond-t1.wSecond<<" s "<<t2.wMilliseconds-t1.wMilliseconds<<" ms";
    return 0;
}