poj 3048 Max Factor（素数筛）

　　这题就是先写个素数筛，存到prime里，之后遍历就好，取余，看是否等于0，如果等于0就更新，感觉自己说的不明白，引用下别人的话吧：

　　素数打表，找出20000之前的所有素数，存入prime数组，对于每个输入的数a，从prime数组最后一个数往前判断，如果a % prime[当前序号]== 0，那么将该素数就是输入数据a的最大素因子，找出所有输入数据的最大素因子，找出最大的那个对应的数据a即可，当a == 1的时候要特别处理。

　　然而我现在还是不懂，为什么输入是1 1的时候输出1，题目也没说啊，还有最蛋疼的就是还是多组数据，题目又没说啊，有木有！！！我找了1小时，最后加个多组数据就A了，让我情何以堪。

#include <bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
typedef long long ll;
#define PI(A) printf("%d
",A)
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)
const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 20000 + 5 ;

//素数筛模板
int prime[MAXN];  //第i个素数
bool is_prime[MAXN+1];//is_prime[i]为true代表i是素数

//返回n以内素数的个数
int sieve(int n)
{
    int p=0;
    for (int i=0; i<=n; i++) is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for (int i=2; i<=n; i++)
    {
        if (is_prime[i])
        {
            prime[p++]=i;
            for (int j=2*i; j<=n; j+=i) is_prime[j]=false;
        }
    }
    return p;
}

int inp[5000+5];

int main()
{
    int n=sieve(MAXN);
    int o;
    
    while(~SI(o))
    {
        for (int i=0; i<o; i++)
            SI(inp[i]);
        int ans=0;
        int k=0;
        for (int i=o-1; i>=0; i--)
        {
            int j;
            for (j=n-1; j>=0; j--)
            {
                if (inp[i]%prime[j]==0)
                {
                    break;
                }
            }
            if (j>=k)
            {
                k=j;
                ans=inp[i];
            }
        }
        //如果ans被更新了 就输出
        if (ans)
            PI(ans);
        //否则 只有全是1的情况，所以输出1
        else puts("1");
    }
    return 0;
}