hdoj2136素数筛选

题目：

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

大致题意：

每个大于等于2的数都由几个素数组成，问满足情况的最大素数是素数表的第几个位置。

由于n最大可取1000000-1，如按常规思路，多半会超时，因此此题可以用素数筛选法。

可以定义一个全局数组，保存0~n的数字为下标，0和1很特殊，直接赋值为0.其余的数暂时清为0.
之后进行筛选，为0的方可值加1，进入内层循环（下标从2开始），然后将它的倍数的值赋为它的值。以此类推。

参考代码：

#include <cstdio> 
using namespace std;
int primes[1000005] = {0};
void mark(int primes[]) {
    int k = 1;
    primes[0] = primes[1] = 0;
    for (int i = 2;i <= 1000000;++i) {
        if (primes[i] == 0) {
            primes[i] = k++;
            for (int j = i * 2;j <= 1000000;j+=i) {
                primes[j] = primes[i];
            }
        }
    }
}
int main() {
    mark(primes);
    int n;
    while (scanf("%d", &n) != EOF) {
        printf("%d\n", primes[n]);
    }
    return 0;
}

有一个坑人的地方：用cin，cout会超时，而用scanf，printf就可以。