[Zadatak] n-cifreni brojeve kod kojih svake pojedinacne cifre su prost broj

[ Notorious91 @ 27.05.2008. 13:03 ] @

Evo jednog zadatka

Rest at the sea is wonderful! However, programmer Pasha became awfully bored of lying on a beach in Turkey; so bored that he decided to count the quantity of three-digit prime numbers. This turned out to be so interesting that he then started to study threeprime numbers. Pasha calls an integer a threeprime number if any three consecutive digits of this integer form a three-digit prime number. Pasha had already started working on the theory of the divine origin of such numbers when some vandals poured water on Pasha and cried some incomprehensible words like “Sonnenstich!”, “Colpo di sole!”, and “Coup de soleil!”

You are to continue Pasha’s work and find out how often (or rare) threeprime numbers are.
Input

The input contains an integer n (3 ≤ n ≤ 10000).
Output

Output the quantity of n-digit threeprime numbers calculated modulo 109 + 9.

Primer: za input uzeti 4 output=204

E sad evo mog koda koji tacno racuna ali sam ga ja previse zakomplikovao,tako da za velike brojeve neci da racuna

Code:

#include <iostream>
#include <math.h>
using namespace std;
long a[170];
long c[1000000];
int main()
{
    long n,n1,b=0,br=0,brr=0,b1;
    int o=1,temp,test=2;

    cin>>n;

    for(int i=1;i<1000;i+=2)
    {
            temp=i;


           test=2;
           for(int x=2;x<temp/2;x++)
           {

           if(temp%x==0)
           {
                         test=1;
                         goto pu;
                         }
                         }
                         if(test=2)
           {
                     a[o]=temp;
                     o++;}
                         pu:;}

                         n1= (long) pow(10,n);

            for(long i=(n1/10);i<=n1;i++)
            {
                     temp=i;


                     for(long i=n;i>0;i--)
                     {
                              c[i]=temp%10;
                              temp/=10;
                              }

                               for(long l=1;l<=n-2;l++)
                               {b1=b;
                                         b=(c[l]*100)+(c[l+1]*10)+c[l+2];
                                         if(b==b1)goto yu;

                                         for(int i=28;i<170;i++)
                                       {
                                                              if(b==a[i]){
                                                              br++;

                                                              goto yu;
                                                              }}yu:;
                                         }
                                         if(br==n-2)
                                         {
                                                    brr++;}
                                                    br=0;}


                        cout<<brr;

                         system("pause");
                         return 0;
                         }

da li neko moze da mi uradi zadatak na jednostavniji nacin tj da se brze izvrsava.Hvala