数学--数论--HDU2136 Largest prime factor 线性筛法变形

Problem Description

代码语言：javascript复制

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

代码语言：javascript复制

Each line will contain one integer n(0 < n < 1000000).

Output

代码语言：javascript复制

Output the LPF(n).

Sample Input

代码语言：javascript复制

1 2 3 4 5

Sample Output

代码语言：javascript复制

0 1 2 1 3

问数的编号，素数的话就是第几个素数就是他的编号如 2-1 3-2 5-3 7-4非素数就是最小的素因子的序号是他的序号。修改后的线筛完事。

代码语言：javascript复制

#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("%lldn", e[n]);
    }
}

input output sample

0 人点赞