URI/BEE 3165/beecrowd | 3165 - Twin Prime

/*

You have to find out two nearest prime numbers of N which have the maximum size less than or equals to N and the gap between them is two.

In this code/algorithm, since the input data is subtle by 10^3, in that case, any naive formulation to find prime numbers is acceptable. Thus, we have applied Sieve to make separate all composite and prime numbers and then the Twin_Prime() function figure out the two adjacent prime numbers in such as way that each number is updated by its adjacent prime number which has a difference is two.

*/

#include<stdio.h>

#define high 1007

#define sf scanf

#define pf printf

int primes[high], flag[high];

void init()

{

    int i=0;

    for(; i<high; i++)

    {

        flag[i] = 0;

    }

}

void Sieve()

{

    int i=0, j=0;

    for(i=2; i<high; i++)

    {

        if(flag[i] == 0)

        {

            //pf("%d ", i);

            for(j=i*i; j<high; j+=i)

            {

                flag[j] = 1; // all composite numbers

            }

        }

    }

}

void Twin_Prime()

{

    int i=6, last_prime = 5;

    primes[5] = 5;

    for(; i<high; i++)

    {

        if(flag[i] == 0 && flag[i - 2] == 0) // finding the two adjacent prime numbers which has difference 2

        {

            last_prime = i; // thus, the prime number is updated by the satisfying one

        }

        primes[i] = last_prime; // any number or index (both composite and prime) is updated by the prime number

    }

//    for(i=5; i<high; i++)

//    {

//        pf("for %d = %d\n", i, primes[i]);

//    }

}

int main()

{

    init();

    Sieve();

    Twin_Prime();

    int N;

    sf("%d", &N);

    pf("%d %d\n", primes[N]-2, primes[N]); 

/* the Twin_Prime() function organized the primes[] array in such a way so that we get the desired first prime number at the back of by 2.*/

    return 0;

}