a569 - 2-絕對遞增的質數子數列

Sylveon

原題：http://zerojudge.tw/ShowProblem?problemid=a569
AC：http://zerojudge.tw/Submissions? ... mp;account=lfs92002
解法：質數表

把質數表建出來後線性掃描即可，懶得IO優化，用STL亂做，用了100多MB的記憶體...

/**********************************************************************************/
/*  Problem: a569 "2-絕對遞增的質數子數列" from 台北市101學年度軟體設計競賽*/
/*  Language: CPP (731 Bytes)                                                     */
/*  Result: AC(1.6s, 112.3MB) judge by this@ZeroJudge                             */
/*  Author: lfs92002 at 2014-06-27 18:52:11                                       */
/**********************************************************************************/


#include<cstdio>
#include<algorithm>
#include<vector>
#include<sstream>

using namespace std;

char input[1000000];
bool isnp[10000001]={true,true,false};

int main()
{
        stringstream ss;
        int i=2,j;
        long long tmp,last,sum,ans;
        while(i<3163){
                if(!isnp[i]){
                        j=i*i;
                        while(j<10000001){
                                isnp[j]=true;
                                j+=i;
                        }
                }
                ++i;
        }       
        while(gets(input)){
                ss.clear();
                ss<<input;
                ans=sum=0;
                last=-1;
                while(ss>>tmp)
                {
                        if(!isnp[tmp])
                        {
                                if(last==-1)last=tmp;
                                if(last<tmp)
                                {
                                        sum+=tmp;
                                }
                                else
                                {
                                        sum=tmp;
                                }
                                ans=max(sum,ans);
                                //printf("%d ",ans);
                                last=tmp;
                        }
                        else
                                sum=0;
                }
                printf("%lld\n",ans);
        }
}