『算法-ACM 竞赛-数学-数论』HDU2136 Largest prime factor 线性筛法变形

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-1 3-2 5-3 7-4 非素数就是最小的素因子的序号是他的序号。修改后的线筛完事。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
int prime[N], cnt;
bool vis[N];
int num[N], e[N], tot = 1;
void init()
{
    for (int i = 2; i <= N; ++i)
    {
        if (!vis[i])
        {
            prime[++cnt] = i;
            num[i] = i + 1;
            e[i] = tot++;
        }
        for (int j = 1; j <= cnt; ++j)
        {
            if (prime[j] * i > N)
                break;
            vis[prime[j] * i] = true;
            e[prime[j] * i] = e[i];
        }
    }
}
int main()
{
    init();

int n;
    while (scanf("%d", &n) != EOF)
    {
        printf("%lld\n", e[n]);
    }
}