P1020 （C++代码）

解题思路:





注意事项:


就明星来啦！！！！


参考代码:

试了三种方法最终还是突破了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20100;
int n,tot=0;
int zhishu[maxn];
bool exist[maxn],done[maxn];
void zhishubiao()
{
 memset(done,0,sizeof(done)); zhishu[++tot]=2;
 memset(exist,0,sizeof(exist)); exist[1]=exist[2]=1;
 for (int i=4;i<=maxn;i+=2) done[i]=1;
 for (int i=3;i<=maxn;i++)
 {
  bool flag=0;
   if (!done[i]) for (int j=2;j*j<=i;j++) 
  {
   if (i%j==0)
   {
    for (int k=i+i;k<=maxn;k+=i) done[k]=1;
    flag=1; break;
   }
  }
  if (flag==0 && done[i]==0) done[i]=exist[i]=1,zhishu[++tot]=i;
 }

/* memset(exist,0,sizeof(exist)); exist[1]=exist[2]=1; zhishu[++tot]=2;
 for (int i=3;i<=maxn;i++)
 {
  bool flag=0;
  for (int j=2;j<i;j++) if (i%j==0) { flag=1; break; } 
  if (!flag) { exist[i]=1; zhishu[++tot]=i; } 
 }
*/
}
int main()
{
 scanf("%d",&n); zhishubiao(); int MAX=0,ans;
 while(n--)
 {
  int x,tt; scanf("%d",&x); tt=x; 
  if (exist[x]) if (MAX<x) { MAX=x; ans=x; }
  if (!exist[x]) for (int i=1;i<=tot;i++)
  {
   if (tt==1) break;
   if (MAX<zhishu[i]) {  MAX=zhishu[i]; ans=x; }
   while(1) { if (tt%zhishu[i]==0) tt/=zhishu[i]; else break; }
  }
 }
 printf("%d\n",ans);
 return 0;
}

不解释了，很简单