传送门
题意
给出若干个数n(n<=1000000)，求每个n的最大质因子的排名。
质数的排名：如果素数p是第k小的素数，那么p的排名就是k。
思路
乍一看不知道怎么搞。
其实可以想想我们怎么筛素数的，每个数都会被它的质因数筛去。
这就和题目一样了。
代码
1 #include <cstdio> 2 3 const int MAXN = 1000001; 4 int notpri[MAXN], cnt = 1; 5 6 int main() 7 14 while(~scanf("%d", &x)) printf("%d\n", notpri[x]); 15 return 0; 16 }View Code
上一篇：[BZOJ1264][AHOI2006]基因匹配Match（DP + 树状数组）
下一篇：[luoguP3606] [USACO17JAN]Building a Tall Barn建谷仓（贪心 + 线段树）
素数筛
