【hihocoder 1295】Eular质数筛法

【题目链接】:http://hihocoder.com/problemset/problem/1295

【题意】

【题解】



可以在O(N)的复杂度内求出1..N里面的所有素数;

当然受空间限制,N可能也就是几百万的样子吧;

再低一点的话用朴素的筛法都能过了；

它的思路主要是;

抓住每个合数的最小的质因数是唯一的这一点;

然后避免每个合数被多次计算到;

因此每次枚举的都是质因数的倍数;

同时i%prim[j]==0直接break掉那点也很巧妙;

这里找到了break掉的原理↓↓

/*

    算法最难理解的是第七行：

    当peimer[j]是i的因子的时候，退出循环，不再进行剔除操作；

    这么做的原因如下：首先peimer[j]是i的最小质因数，因为j是从0开始的；

    其次,我们可以肯定的说,i已经无需再去剔除prime[j']*i (j'>j) 形式的合数了,这是因为,prime[j']*i可以写成

    prime[j']*(prime[j]*k)

    =

    prime[j]*(prime[j']*k),

    也就是说所有的prime[j']*i将会被将来的某个i'=prime[j']*k剔除掉，当前的i已经不需要了。

*/

【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1e6+100;

bool iszs[N];

vector <int> zsb;

int n;

int main()

{

    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use

    ms(iszs,true);

    cin >> n;

    rep1(i,2,n)

    {

        if (iszs[i]) zsb.pb(i);

        int len = zsb.size();

        rep1(j,0,len-1)

        {

            int t = zsb[j];

            if (i*t>n) break;

            iszs[i*t] = false;

            if (i%t==0) break;

        }

    }

    cout << zsb.size() << endl;

    return 0;

}