题目：给一个数n，求它的最大质因数是第几个质数，1的为0, 2,3，5,7...分别为1,2,3,4......
分析：先打表吧1到1000000的质数到找出来放到prime[]，在查找一直TLE....
，参考了别人的思想，开一个数组prime【i】，先把2的倍数，赋值为1,3的倍数赋值为2，5的倍数赋值为3，..........以此类推....为了方便找质数，开一个数组vis【】吧访问过的合数全赋值为1，
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1000100;
int prime[maxn];
int vis[maxn];
int main()
{
int n,c=0;
memset(vis,0,sizeof(vis));
prime[1]=0;
for(int i=2;i<=maxn;i++)
{
if(vis[i]==0)
{
c++;
for(int j=i;j<=maxn;j+=i)
{
prime[j]=c;
vis[j]=1;
}
}
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",prime[n]);
}
system("pause");
return 0;
}
把ＴＬＥ的代码也放这里吧．．．．．希望以后能自己找到更高效的算法：
/*
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
const int maxn=1000100;
int prime[maxn];
int vis[maxn];
int main()
{
//筛素数
int num=1;
memset(vis,0,sizeof(vis));
for(int i=2;i<=maxn;i++)
{
/*
int flag=1;
for(int j=2;j<=(int)sqrt(i+0.5);j++)
{
if(i%j==0)
{
flag=0;
break;
}
}
if(flag==1)
{
prime[num++]=i;
}
}*/
if(!vis[i])
{
prime[num++]=i;
for(int j=i*i;j<=maxn;j+=i)
vis[j]=1;////????????????
}
for(int j=i*2;j<=maxn;j+=i)
vis[j]=1;
}
for(int i=2;i<=maxn;i++)
if(vis[i]==0)
prime[num++]=i;
//***********************
for(int i=1;i<=100;i++)
{
printf("%d ",prime[i]);
if(i%10==0)
printf("\n");
}
int primesum=num-1;
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==1)
{
printf("0\n");
continue;
}
for(int i=(primesum<n?primesum:n);i>=1;i--)
{
if(n%prime[i]==0)
{
printf("%d\n",i);
break;
}
}
}
system("pause");
return 0;
}