Solve of UVA 12542: Prime Substring
#include<iostream>
#include<stdio.h>
using namespace std;
int mx = 100000;
int arr[100010]={0};
void civ()
{
int i,j,n;
arr[0]=arr[1]=1;
for(i=2;i*i<=mx;i++)
{
if(arr[i]==0)
{
for(j=2*i;j<=mx;j+=i)
arr[j]=1;
}
}
}
int main()
{
civ();
int i,j,k,l,n,m,st[260],mn;
string x;
while(getline(cin,x))
{
if(x[0]=='0' && x[1]=='\0')
return 0;
l=x.size();
for(i=0;i<l;i++)
{
st[i]=x[i]-'0';
}
mn=-1;
for(i=0;i<l;i++)
{
m=0;
for(j=i;j<l;j++)
{
m=m*10+st[j];
if(m>mx)
break;
else if(arr[m]==0)
mn=max(mn,m);
//cout<<m<<endl;
}
}
cout<<mn<<endl;
}
return 0;
}
No comments:
Post a Comment