本文共 702 字，大约阅读时间需要 2 分钟。

Problem Description

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.

 

 

Input

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

 

 

Output

Output the LPF(n).

 

 

Sample Input

1

2

3

4

5

 

 

Sample Output

0

1

2

1

3

通过素数筛的过程中来求得最大素数因子。。。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn=1000010;int Isn[maxn];int n;vector
         
          ve;int loc[maxn];void init(){ memset (Isn,0,sizeof(Isn));}void Is_prime(){ loc[1]=0; for (int i=2,k=1;i
         
        
       
      
     
    
   

 

转载地址：http://lxaen.baihongyu.com/