sdnu1522.陆历川学数学(素数筛)

Description

陆历川很热爱数学，最近他学了质数，他被质数深深的吸引了，但是陆历川有个习惯，他喜欢给一些东西编号，所以他决定给所有的质数编号，例如给2编号1，3编号2，5编号3........这样2，3，5就是质数里面的大当家，二当家和三当家了，陆历川现在知道了这些编号，现在他会给你一个数，他想知道这个数的所有的质因子里面的最大编号是多少？

注：0和1的编号都是0。

Input

一个自然数N(0<= N <= 1000000)

多组输入样例

Output

最大编号

Sample Input

1
2
3
4
5

Sample Output

0
1
2
1
3

一开始以为要用lower_bound(),T了一发后发现能直接存储。

对于每个数，在筛素数的过程中保存此时素数编号，直接访问即可。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int vis[N];
int cnt;
void E()
{
    cnt=1;
    memset(vis,0,sizeof(vis));
    for(int i=2; i<N; i++)
    {
        if(!vis[i])
        {
            vis[i]=cnt;
            for(int j=i+i; j<N; j+=i)
                vis[j]=cnt;
            cnt++;
        }
    }
}
int main()
{
    int n;
    E();
    while(scanf("%d",&n)!=EOF)
    {
        cout<<vis[n]<<'\n';
    }
    return 0;
}