HDU 2136 Largest prime factor

题意：

求一个不超过1000000数的最大素因子的排位，1排0号，2排1号，5排3号......

题解：

/*
n最大不超过1000000，可以枚举每一个数i，与小于它的数j进行乘积，得到的数n的最大质因子的排序是i和j中大的那一个 
*/
#include <iostream>

using namespace std;

int num[1000006];

int main()
{
    for (int i = 0; i < 1000000; ++i) num[i] = -1;
    num[1] = 0;
    int k = 0;
    for (int i = 2; i < 1000000; ++i) {
        if (num[i] == -1) {
            num[i] = ++k;
        }
        for (int j = 2; j <= i; ++j) {
            int temp = i * j;
            if (temp >= 1000000) break;
            num[temp] = max(num[temp], max(num[i], num[j]));
        }
    }
    int n;
    while (~scanf("%d", &n)) {
        cout << num[n] << endl;
    }
    return 0;
}