sdnu1522.陆历川学数学(素数筛)
Description
陆历川很热爱数学，最近他学了质数，他被质数深深的吸引了，但是陆历川有个习惯，他喜欢给一些东西编号，所以他决定给所有的质数编号，例如给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
Sample Output
0 1 2 1 3
一开始以为要用lower_bound(),T了一发后发现能直接存储。
对于每个数，在筛素数的过程中保存此时素数编号，直接访问即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int vis[N];
int cnt;
void E()
{
cnt=1;
memset(vis,0,sizeof(vis));
for(int i=2; i<N; i++)
{
if(!vis[i])
{
vis[i]=cnt;
for(int j=i+i; j<N; j+=i)
vis[j]=cnt;
cnt++;
}
}
}
int main()
{
int n;
E();
while(scanf("%d",&n)!=EOF)
{
cout<<vis[n]<<'\n';
}
return 0;
}
查看3道真题和解析
加油！