HDU 2710 ( Max Factor )

//记住这里的1被认为是素数
Problem : 2710 ( Max Factor )     Judge Status : Accepted
RunId : 5596642    Language : C++    Author : ssun
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta

#include<iostream>
#include<string>
using namespace std;

const int N = 20050;
int main()
{
    int i,j,cnt,maxnum;
    int n;
    int arr[5005];
    int prime[N];
    for(i=0; i<N; i++) prime[i]=1;
    for(i=2; i<N; i++)
    {
        for(j=i+i; j<N; j=j+i)
        {
            if(prime[i]!=0)
                prime[j] = 0;
        }
    }
    
    while(cin>>n)
    {
        maxnum=-1;
        for(i=0; i<n; i++)
        {
            
            cin>>arr[i];
        //    cout<<arr[n]<<endl;
            for(j=arr[i]; j>0; j--)
            {
                if(prime[j]!=0 && arr[i]%j==0)
                {
                    if(maxnum<j) 
                    {
                        maxnum = j;
                        cnt = i;
                    }
                    break;
                }
            }        
        }
        cout<<arr[cnt]<<endl;
    }
    return 0;
}