449C - Jzzhu and Apples - CodeForces Solution

#include <iostream>

#include <cstdio>

#include <string>

#include <algorithm>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <deque>

#include <set>

#include <map>

#include <climits>

#include <cstdlib>

#include <string.h>



using namespace std;



#define For(i,i1,i2) for(int i=(int)i1 ; i<=(int)i2 ; i++)

#define Rof(i,i1,i2) for(int i=(int)i1 ; i>=(int)i2 ; i--)

#define int long long

#define NMAX 400005

#define PMAX 100005

#define MODU 1000000007

#define pii pair<int,int>

#define xx first

#define yy second

#define mp make_pair

#define pb push_back



vector<int> even,ans,hold;

int n;

int p[PMAX];

int check[NMAX];



void sieve_prime()

{

    p[0] = p[1] = 1;

    For(i,2,PMAX-1)

    if (p[i]==0)

    {

        for(int j=i*i ; j<PMAX ; j+=i)

            p[j] = i;



    }

}



void solve()

{

    For(i,3,n/2)

    if (p[i]==0)

    {

        int t = n/i;

        hold.clear();

        For(j,1,t)

        if (check[i*j]==0)

        {

            check[i*j] = 1;

            hold.pb(i*j);

        }

        if ((int)(hold.size())%2)

        {

            int flag = 0;

            int it = 0;

            while (it<(int)hold.size())

            {

                if (flag==0 && hold[it]%2==0)

                {

                    flag = 1;

                    even.pb(hold[it]);

                }

                else

                    ans.pb(hold[it]);

                it++;

            }

        }

        else

            for(int num:hold)

                ans.pb(num);

    }

    For(i,2,n)

        if (i%2==0 && check[i]==0) even.pb(i);

    for(int i=0 ; i<(int)even.size()-1 ; i+=2)

    {

        ans.pb(even[i]);

        ans.pb(even[i+1]);

    }

    printf("%I64d\n",(int)ans.size()/2);

    for(int i=0 ; i<ans.size() ; i+=2)

    {

        printf("%I64d %I64d\n",ans[i],ans[i+1]);

    }

}



main()

{

    #ifndef ONLINE_JUDGE

    freopen("a.inp","r",stdin);

    #endif // ONLINE_JUDGE



    sieve_prime();

    scanf("%I64d\n",&n);

    solve();

}