fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. // quick sieve primes below n
  6. int sieve(int n,int**p,int*l){
  7.  if(n<2) return -1;
  8.  else if(n==2){
  9.   *l=1;
  10.   *p=(int*)malloc(*l*sizeof(int));
  11.   (*p)[0]=2;
  12.   return 0;
  13.  }
  14.  int tmpl=(n+1-3+1)/2;
  15.  int *s=(int*)malloc(tmpl*sizeof(int));
  16.  double mr=sqrt(n);
  17.  int i=0,m=3,j,h=(n+1)/2-1;
  18.  for(;i<tmpl;i++) s[i]=3+2*i;
  19.  i=0;
  20.  while(m<=mr){
  21.   if(s[i]){
  22.    j=(m*m-3)/2;
  23.    s[j]=0;
  24.    while(j<h){
  25.     s[j]=0;
  26.     j+=m;
  27.    }
  28.   }
  29.   i++;
  30.   m=2*i+3;
  31.  }
  32.  h=1;
  33.  for(i=0;i<tmpl;i++) if(s[i]) h++;
  34.  *p=(int*)malloc(h*sizeof(int));
  35.  (*p)[0]=2;
  36.  h=1;
  37.  for(i=0;i<tmpl;i++)
  38.   if(s[i]) (*p)[h++]=s[i];
  39.  free(s);
  40.  *l=h;
  41.  return 0;
  42. }
  43.  
  44. // test for primality
  45. int ispr(int n){
  46.  double m=1+sqrt(n);
  47.  if(n%2==0) return 0;
  48.  int d=3;
  49.  while(d<m){
  50.   if(n%d==0)return 0;
  51.   d+=2;
  52.  }
  53.  return 1;
  54. }
  55.  
  56. int digits(int n){
  57.  return (int)(1+floor(log(n)/log(10)));
  58. }
  59.  
  60. int pow_10[]={1,10,100,1000,10000};
  61.  
  62. // test if n can form prime with numbers from l
  63. int test(int*l,int ll,int n){
  64.  int i=0,y,yd,nd=digits(n);
  65.  for(;i<ll;i++){
  66.   y=l[i];
  67.   yd=digits(y);
  68.   if(!(ispr(y*pow_10[nd]+n)&&ispr(n*pow_10[yd]+y)))
  69.    return 0;
  70.  }
  71.  return 1;
  72. }
  73.  
  74. int main() {
  75.  int *pr=NULL,N=0;
  76.  sieve(10000,&pr,&N);
  77. #define K 5
  78.  int l[K];
  79.  int c0,c1,c2,c3,c4;
  80.  
  81.  for(c0=0;c0<N-K+1;c0++){
  82.   l[0]=pr[c0];
  83.   for(c1=c0+1;c1<N-K+2;c1++){
  84.    if(test(l,1,pr[c1])){
  85.     l[1]=pr[c1];
  86.     for(c2=c1+1;c2<N-K+3;c2++){
  87.      if(test(l,2,pr[c2])){
  88.       l[2]=pr[c2];
  89.       for(c3=c2+1;c3<N-K+4;c3++){
  90.        if(test(l,3,pr[c3])){
  91.         l[3]=pr[c3];
  92.         for(c4=c3+1;c4<N-K+5;c4++){
  93.          if(test(l,4,pr[c4])){
  94.           l[4]=pr[c4];
  95.           printf("%d, %d, %d, %d, %d (%d)\n",
  96.            l[0],l[1],l[2],l[3],l[4],l[0]+l[1]+l[2]+l[3]+l[4]);
  97.           goto EXIT;
  98.          }
  99.         }
  100.        }
  101.       }
  102.      }
  103.     }
  104.    }
  105.   }
  106.  }
  107.  
  108. EXIT:
  109.  free(pr);
  110.  return 0;
  111. }
  112.  
Success #stdin #stdout 1.69s 1804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
13, 5197, 5701, 6733, 8389 (26033)
https://ideone.com/0Ih6L
language:
C (gcc 8.3)
created:
16 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!