2428: Super Prime
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 |
3s | 8192K | 313 | 88 | Standard |
In these days, skywind had thought a series of new problem. But he must keep these problem for the coming important contests such as "JiLin Provincial Collegiate Programming Contest" and "The 2007 ACM Asia Programming Contest Changchun Site Network Preliminary Contest". This time, he brings out a easy problem.
Superprime is such integer that all part of it from lowest digit is prime. For example, 9547 is a superprime because 7, 47, 547 and 9547 is all prime. Given a index i, your task is to find the i-th superprime. Noting that in this problem, 1 is considered as a prime, but 2 is NOT.
Input and Output
Each line of input is a integer i, that you should print the i-th superprime in each line. The maximal superprime in output is less than 10^9;
Sample Input
1 2 212
Sample Output
1 3 9547
Problem Source: skywind
#include<iostream>
#include<cmath>
using namespace std;
int prime[40000],is[40000],flag[40000];
int pl;
int isprime(int n)
{
double k=sqrt(n);
for(int i=0;is[i]<=k;i++)
{
if(n%is[i]==0) return 0;
}
return 1;
}
int main()
{
for(int i=2;i<40000;i++)
{
if(flag[i]==0) is[pl++]=i;
for(int j=0;j<pl&&i*is[j]<40000;j++)
{
flag[i*is[j]]=1;
if(i%is[j]==0) break;
}
}
int base[10];
base[1]=1;
for(int i=2;i<10;i++) base[i]=base[i-1]*10;
prime[0]=1;
for(int i=1;i<4;i++) prime[i]=is[i];
int temp_begin=0,temp_end=4,cnt=4;
for(int t=2;t<10;t++)
{
for(int s=1;s<10;s++)
{
int p=s*base[t];
for(int i=temp_begin;i<temp_end;i++)
{
int m=p+prime[i];
if(isprime(m)) prime[cnt++]=m;
}
}
temp_begin=temp_end;temp_end=cnt;
}
int n;
while(cin>>n)
{
cout<<prime[n-1]<<endl;
}
return 0;
}