SGU 116. Index of super-prime Solution

116. Index of super-prime time limit per test: 0.5 sec.  memory limit per test: 4096 KB Let P1, P2, … ,PN, … be a sequence of prime numbers. Super-prime number is such a prime number that its current number in prime numbers sequence is a prime number too. For example, 3 is a super-prime number, but 7 is not. Index of super-prime for number is 0 iff it is impossible to present it as a sum of few (maybe one) super-prime numbers, and if such presentation exists, index is equal to minimal number of items in such presentation. Your task is to find index of super-prime for given numbers and find optimal presentation as a sum of super-primes. Input There is a positive integer number in input. Number is not more than 10000. Output Write index I for given number as the first number in line. Write I super-primes numbers that are items in optimal presentation for given number. Write these I numbers in order of non-increasing. Sample Input 6 Sample Output 2 3 3   Solution : Here,is the C implementation of this problem.

#include <cstdio>
#include <iostream>

using namespace std;

#define sz 10001
#define hi 101
#define nSuperPrime 201

bool prime[sz];
int primeTable[1230],nPrime,superPrime[nSuperPrime];

void sieve(){
 int i,j;

 for( i=4; i < sz ;i += 2)
  prime[i] = true;

 primeTable[nPrime++] = 2;

 for( i=3; i <= hi;i += 2){
  if(!prime[i]){
   primeTable[nPrime++] = i;
   for(j = i+i; j < sz; j += i)
    prime[j] = true;
  }
 }
 for( i= hi+2; i < sz; i += 2)
  if(!prime[i])
   primeTable[nPrime++] = i;
}

typedef struct{
 int cnt,prev;
}data;
data tmp[sz];



int main(){
 int i,j,t,high,n;

 sieve();

 for(i = 0; i < sz; i++)//used for precalculation
  tmp[i].cnt = sz,tmp[i].prev = 0;


 for(i=0; primeTable[i] <= nPrime; i++){//saving superPrime
  superPrime[i] = primeTable[primeTable[i]-1];
 }

 tmp[0].cnt = 0;
 for(i = 0; i < nSuperPrime; i++){//finding out ans
  high = sz - superPrime[i];
  for(j = 0; j < high; j++){
   if(tmp[j].cnt != sz && ( tmp[j].cnt + 1 < tmp[j+superPrime[i]].cnt)){
    tmp[j+superPrime[i]].cnt = tmp[j].cnt + 1;
    tmp[j+superPrime[i]].prev = j;
   }
  }
 }

 while(scanf("%d",&n) == 1){
  if(tmp[n].cnt == sz)
   printf("0\n");
  else{
   printf("%d\n",tmp[n].cnt);
   printf("%d",n - tmp[n].prev);
   t = tmp[n].prev;
   while(t){
    printf(" %d",t - tmp[t].prev);
    t = tmp[t].prev;
   }
   printf("\n");
  }
 }
 return 0;
}