CodeforcesSolvedProblems/Codeforces_DesignTutorialFromMath.cpp at master · JoyCmollik/CodeforcesSolvedProblems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long int ulli;
const int MAXI = 1e6 + 5;

vector<bool> getPrime()
{
 vector<bool> prime(MAXI, true);
 prime[0] = false;
 prime[1] = false;

 for (ulli i = 2; i <= sqrt(MAXI); i++)
 {
  if (prime[i])
  {
   for (ulli x = i * 2; x < MAXI; x += i)
   {
    prime[x] = false;
   }
  }
 }
 return prime;
}

int main()
{
 vector<bool> primeList = getPrime();

 ulli n;
 cin >> n;

 if (n % 2 == 0 && primeList[n / 2] == false)
 {
  cout << n / 2 << " " << n / 2 << endl;
 }
 else if (n % 2 == 0 && primeList[n / 2] == true)
 {
  ulli dive = n / 2;
  ulli divextra = dive;

  while (1)
  {
   if (primeList[dive] == false && primeList[divextra] == false)
   {
    cout << dive << " " << divextra << endl;
    break;
   }
   else
   {
    dive++;
    divextra--;
   }
  }
 }
 else
 {
  ulli dive = n / 2;
  ulli divextra = (n / 2) + 1;

  while (1)
  {
   if (primeList[dive] == false && primeList[divextra] == false)
   {
    cout << dive << " " << divextra << endl;
    break;
   }
   else
   {
    dive--;
    divextra++;
   }
  }
 }
 return 0;
}