先看题：

题目描述

题目链接
陆历川很热爱数学，最近他学了质数，他被质数深深的吸引了，但是陆历川有个习惯，他喜欢给一些东西编号，所以他决定给所有的质数编号，例如给2编号1，3编号2，5编号3……..这样2，3，5就是质数里面的大当家，二当家和三当家了，陆历川现在知道了这些编号，现在他会给你一个数，他想知道这个数的所有的质因子里面的最大编号是多少？
注：0和1的编号都是0。

Input

一个自然数N(0<= N <= 1000000)
多组输入样例

Output

最大编号

Sample Input

1
2
3
4
5
1
2
3
4
5

Sample Output

1
2
3
4
5
0
1
2
1
3

题解

思路： 只要求求最大的素因数的所在编号。我一开始的思路是求出这个数的质因数， 然后排序找最大， TLE，之后不论是遍历n还是遍历素数集， 都TLE了，搜了一下才想到在编号上做文章。
根据这一题， 埃氏筛的那一点点瑕疵就没有了。 具体怎么变得请看下面代码注释

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include "algorithm"
#include "cstdio"
#include "queue"
#include "set"
#include "cstring"
#include "string"
#include "map"
#include "vector"
#include "math.h"
#include "utility"   // pair头文件
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 5;
const int M = 1e9;
int pri[N];
int ma[N];
bool is[N];
int len = 0;
void sushu(int n){
    memset(is, true, sizeof is);
    is[0] = is[1] = 0;
    for (int i = 2; i <= n; i++){
        if (is[i]){
            pri[len++] = i;
            ma[i] = len;
            for (int j = 2 * i; j <= n; j += i){
                is[j] = 0;
                ma[j] = len; // 在这， 每一次更新， 都是的答案更正确化
            }
        }
    }
}

int main(){
    sushu(1000000);
    int n;
    while(~scanf("%d", &n)){
        printf("%d\n", ma[n]);
    }
    return 0;
}

举一反三：如何求出这个最大素因子？

根据上面的题我们可知求出了这个最大素因子的编号，我们直接输出pri[ma[i] - 1]就可，当然，根据这个题很容易看出， 要是脱落了这个题呢？

1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan