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 i=0,c[K]={0},cf[K]={N-K+1,N-K+2,N-K+3,N-K+4,N-K+5};
  80.  for(i=1;i<K;i++)c[i]=-1;
  81.  i=c[0]=0;
  82.  
  83.  while(1){
  84.   // jump out of the loop?
  85.   if(!(c[i]<cf[i])){
  86.    if(i==0){
  87.     break;
  88.    }
  89.    c[i]=-1;
  90.    i-=1;
  91.    c[i]+=1;
  92.    continue;
  93.   }
  94.   // init loop?
  95.   if(c[i]==-1){
  96.    c[i]=c[i-1]+1;
  97.   }
  98.   l[i]=pr[c[i]];
  99.   // start new loop
  100.   if(i==0 || test(l,i,pr[c[i]])){
  101.    i+=1;
  102.    if(i==K){
  103.     // most inner loop body
  104.     printf("%d %d %d %d %d (%d)\n",l[0],l[1],l[2],l[3],l[4],l[0]+l[1]+l[2]+l[3]+l[4]);
  105.     break;
  106.    }
  107.   }else{
  108.    c[i]+=1;
  109.   }
  110.  }
  111.  
  112.  free(pr);
  113.  return 0;
  114. }
  115.  
Success #stdin #stdout 1.72s 1804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
13 5197 5701 6733 8389 (26033)
https://ideone.com/CdQzt
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!