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

 

这道题要用到埃氏筛，前面我发表过埃氏筛的模板，但是不能生搬硬套，因为此处的要求不一样。

#include
     
      #include
      
       #include
       
        using namespace std;#define ll long long#define maxn 1000000+8ll tot,pri[maxn],s[maxn];bool is[maxn];void Eratosthenes(){    tot=0;    memset(is,1,sizeof(is));//定义is数组中所有数都为1；即假设所有数都为素数，方便后面筛出素数    is[0]=is[1]=0;//数字0和1的素数都为0    for(int i=2;i