#include #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++) using namespace std; templateinline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;} templateinline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;} typedef long long ll; // yukicoder No.1006 Share an Integer // 2020.06.21 vector XX; // auto MP = PrimeFac(N); // for(auto i : MP){ // cout << i.first << " " << i.second << endl; // } map PrimeFac(int n){ map mp; int cnt = 0; while(n%2 == 0){ n /= 2; cnt++; } if(cnt != 0) mp[2] = cnt; for(int i = 3; i*i <= n; i += 2){ cnt = 0; while(n%i == 0){ n /= i; cnt++; } if(cnt != 0) mp[i] = cnt; } if(n != 1) mp[n] = 1; return mp; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int X; cin >> X; XX.assign(X, 1e9); XX[1] = 0; for(int i = 2; i < X; i++){ auto x = PrimeFac(i); int res = 1; for(auto j : x){ res *= j.second+1; } XX[i] = abs(i-res); } priority_queue, vector>, greater > > pq; for(int i = 1; i < X; i++){ pq.push({abs(XX[i]-XX[X-i]),i}); } bool flag = true; int minV = 1e9; while(flag){ auto cur = pq.top(); pq.pop(); if(cur.first <= minV){ minV = cur.first; cout << cur.second << " " << X-cur.second << endl; }else{ flag = false; } } }