竹園論壇

標題: a569 - 2-絕對遞增的質數子數列 [打印本頁]

作者: Sylveon 時間: 2014-6-27 19:03
標題: a569 - 2-絕對遞增的質數子數列
原題：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);
}
}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)