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++; } } } }
