/** * author: otera **/ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long typedef long long ll; typedef unsigned long long ul; typedef unsigned int ui; typedef long double ld; const int inf=1e9+7; const ll INF=1LL<<60 ; const ll mod=1e9+7 ; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef complex Point; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair P; typedef pair LDP; typedef pair LP; #define fr first #define sc second #define all(c) c.begin(),c.end() #define pb push_back #define debug(x) cerr << #x << " = " << (x) << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } // isprime[n] := is n prime? // mebius[n] := mebius value of n // min_factor[n] := the min prime-factor of n struct Eratos { vector primes; vector isprime; vector mebius; vector min_factor; Eratos(int MAX) : primes(), isprime(MAX+1, true), mebius(MAX+1, 1), min_factor(MAX+1, -1) { isprime[0] = isprime[1] = false; min_factor[0] = 0, min_factor[1] = 1; for (int i = 2; i <= MAX; ++i) { if (!isprime[i]) continue; primes.push_back(i); mebius[i] = -1; min_factor[i] = i; for (int j = i*2; j <= MAX; j += i) { isprime[j] = false; if ((j / i) % i == 0) mebius[j] = 0; else mebius[j] = -mebius[j]; if (min_factor[j] == -1) min_factor[j] = i; } } } // prime factorization vector> prime_factors(int n) { vector > res; while (n != 1) { int prime = min_factor[n]; int exp = 0; while (min_factor[n] == prime) { ++exp; n /= prime; } res.push_back(make_pair(prime, exp)); } return res; } // enumerate divisors vector divisors(int n) { vector res({1}); auto pf = prime_factors(n); for (auto p : pf) { int n = (int)res.size(); for (int i = 0; i < n; ++i) { int v = 1; for (int j = 0; j < p.second; ++j) { v *= p.first; res.push_back(res[i] * v); } } } return res; } }; void solve() { int x; cin >> x; vector f(x + 1, 0); Eratos er(x); for(int i = 1; i <= x; ++i) { // int cnt = 0; // for(int j = 1; j * j <= i; ++j) { // if(i % j == 0) { // if(j * j == i) { // cnt ++; // } else { // cnt += 2; // } // } // } f[i] = i - er.divisors(i).size(); } vector

res; int mini = inf; for(int a = 1; a <= x - 1; ++a) { if(mini > abs(f[a] - f[x - a])) { mini = abs(f[a] - f[x - a]); res.clear(); res.push_back(P{a, x - a}); } else if(mini == abs(f[a] - f[x - a])) { res.push_back(P{a, x - a}); } } for(auto p: res) { cout << p.fr << " " << p.sc << endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); //cout << fixed << setprecision(10); //int t; cin >> t; rep(i, t)solve(); solve(); return 0; }