hdu 2136 Largest prime factor【数论、动态规划、二分查找】
http://acm.hdu.edu.cn/showproblem.php?pid=2136
【题目大意】
求一个数的最大素因子是第几个素数。
【解题思路】
有两种思路，第一种是分解素因子，求得最大素因子，然后二分查找素数表，得到是第几个素因子，代码如下：
【提交情况】
多次tle，因为考虑到可能时间要求不那么严格，找素数的时候没有二分查找。
#include <iostream>
#include <cstdio>
using namespace std;
long prime(long a[],long n)
{
long i,j,k,x,num,*b;
n++;
n/=2;
b=new long[(n+1)*2];
a[0]=2;a[1]=3;num=2;
for(i=1;i<=2*n;i++)
b[i]=0;
for(i=3;i<=n;i+=3)
for(j=0;j<2;j++)
{
x=2*(i+j)-1;
while(b[x]==0)
{
a[num++]=x;
for(k=x;k<=2*n;k+=x)
b[k]=1;
}
}
return num;
}
long p[110000];
int main()
{
long in,i,tmpIn,pNum,dn,up,mid;
pNum=prime(p,1100000);
while(scanf("%ld",&in)!=EOF)
{
for(i=0;p[i]*p[i]<=in;i++)
{
if(in%p[i]==0) while(in%p[i]==0) in/=p[i];
}
if(in==1) printf("%ld\n",i);
else
{
dn=0; up=pNum;
while(dn<up)
{
mid=(dn+up)/2;
if(p[mid]==in) break;
else if(p[mid]>in) up=mid;
else dn=mid;
}
if(mid+1>i) printf("%ld\n",mid+1);
else printf("%ld\n",i);
}
}
return 0;
}