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

 

题解：素数筛 普通筛法

时间复杂度：$O(N * lnN)$

代码：

#include 
       
        using namespace std;const int maxn = 1e6 + 10;int a[maxn];int main() {    int N, k = 1;    memset(a, 0, sizeof(a));    for(int i = 2; i < maxn; i ++) {        if(a[i] == 0) {            a[i] = k++;            for(int j = i + i; j < maxn; j += i)            a[j] = a[i];        }    }    while(~scanf("%d", &N)) {        printf("%d\n", a[N]);    }    return 0;}