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\n",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- ;

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

const int MAXN=  +  ;

//素数筛模板

int prime[MAXN];  //第i个素数

bool is_prime[MAXN+];//is_prime[i]为true代表i是素数

//返回n以内素数的个数

int sieve(int n)

{

    int p=;

    for (int i=; i<=n; i++) is_prime[i]=true;

    is_prime[]=is_prime[]=false;

    for (int i=; i<=n; i++)

    {

        if (is_prime[i])

        {

            prime[p++]=i;

            for (int j=*i; j<=n; j+=i) is_prime[j]=false;

        }

    }

    return p;

}

int inp[+];

int main()

{

    int n=sieve(MAXN);

    int o;

    while(~SI(o))

    {

        for (int i=; i<o; i++)

            SI(inp[i]);

        int ans=;

        int k=;

        for (int i=o-; i>=; i--)

        {

            int j;

            for (j=n-; j>=; j--)

            {

                if (inp[i]%prime[j]==)

                {

                    break;

                }

            }

            if (j>=k)

            {

                k=j;

                ans=inp[i];

            }

        }

        //如果ans被更新了 就输出

        if (ans)

            PI(ans);

        //否则 只有全是1的情况，所以输出1

        else puts("");

    }

    return ;

}

巴特西

poj 3048 Max Factor（素数筛）

最新文章

热门文章