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

题目大意：每个素数在素数表中都有一个序号，设1的序号为0，则 2

的序号为1（4是2的倍数，所以4的序列也是1），3的序号为2，5的序号为3，以此类推。现在要求输出 所

给定的数n的最大质因子的序号，0 < n < 1000000。

思路：巧用素数打表法。用sum计算素数的序号，将素数连同他的倍数一起置为它的素数序号， 从小到大循环， 这样数组里存放的序号就是最大素数因子的序号了。

注意：初始化时令所有数为0。

再通过sum计算累加，改变之后primeNum[i]为 数 i的最大素数因子的序号。

import java.util.Arrays;

import java.util.Scanner;

public class Main{

    static int primeNum[] = new int[1000002];

    public static void main(String[] args) {

        dabiao();

        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {

            int n = sc.nextInt();

            System.out.println(primeNum[n]);

        }

    }

    private static void dabiao() {

        int sum = 1;

        Arrays.fill(primeNum, 0);

        for (int i = 2; i < primeNum.length; i++) {

            if (primeNum[i] == 0) {

                for (int j = i; j < primeNum.length; j = j + i) {

                    primeNum[j] = sum;

                }

                sum++;

            }

        }

    }

}