UVA Problem 10168 Solution

Problem Solving, UVa

 

#include <stdio.h>



#define N 10000000



typedef long long LL;



using namespace std ;



LL primes[N];

//bool flag[N];



void sieve(LL n)

{

for(LL i=4; i<=n; i+=2)

{

    primes[i]=1;

}

//LL p=(LL)sqrt(n);

for(LL i=3; i*i<=n; i+=2)

{

    if(primes[i])

   

    continue;

        //primes[cnt++]=i;

    //    if(i <= n/i)

    //    {

            for(LL j=i*i; j<=n; j+=i*2)

            {

                primes[j] = 1;

            }

    //    }

    }



return ;

}

/*bool isprimes(LL x)

{

    for(LL i=0;;i++)

    {

        if(primes[i]*primes[i] >x )

        break;

        if(x%primes[i]==0)

        return false;

    }

    return true;

}*/



void res(LL x)

{



    for(LL i=2;;i++)

    {

    //LL p1=primes[i];

//    LL p2= primes[x-i];

        if( !primes[i] && !primes[x-i] )

        {

            printf("%lld %lld",i,x-i );

            break;

        }

    }

}



int main()

{

    LL n;

    sieve(N);

    while(scanf("%lld",&n)!=EOF){

        if(n<=7){

            printf("Impossible.");

            continue;

        }

        if(n&1){

            printf("2 3 ");

            res(n-5);

        }

        else{

            printf("2 2 ");

            res(n-4);

        }

        puts("");

    }

     return 0 ;

}

 

0 Comments

You may find interest following article