Everybody knows any number can be combined by the prime number. 

Now, your task is telling me what position of the largest prime factor. 

The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc. 

Specially, LPF(1) = 0. 

InputEach line will contain one integer n(0 < n < 1000000). 

OutputOutput the LPF(n). 

Sample Input

12345

Sample Output

01213

 

对x分解质因数，问最大的质因子是第几大质数

瞎暴力就好

1 #include
      
        2 #include
       
         3 #define LL long long 4 using namespace std; 5 inline LL read() 6 { 7     LL x=0,f=1;char ch=getchar(); 8     while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();} 9     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}10     return x*f;11 }12 int mk[1000010];13 int pp[300010],len;14 int rnk[1000010];15 int n;16 inline void getp()17 {18     for (int i=2;i<=1000000;i++)19     {20         if (!mk[i])21         {22             for (int j=2*i;j<=1000000;j+=i)mk[j]=1;23             pp[++len]=i;24             rnk[i]=len;25         }26     }27 }28 int main()29 {30     getp();31     while (~scanf("%d",&n))32     {33         if (!mk[n]){printf("%d\n",rnk[n]);continue;}34         int mx=0;35         for (int i=1;i<=len;i++)36         {37             if (pp[i]*pp[i]>n)break;38             if (n%pp[i]==0)mx=i;39             while (n%pp[i]==0)n/=pp[i];40         }41         if (n!=1)mx=rnk[n];42         printf("%d\n",mx);43     }44 }