#include using namespace std; #define int long long const int MAX_N = 2e6+10; const int inf = 1e9; bool arr[MAX_N]; int division[MAX_N]; set se; void eratosthenes(){ for(int i = 0; i < MAX_N; i++){ arr[i] = true;} arr[0] = false; arr[1] = false; for(int i = 2; i < MAX_N; i++){ //素因数列挙 if(arr[i] ){ for(int j = 2; i*j < MAX_N; j++){ arr[i*j] = false; } } } for(int i = 0; i < (int)sqrt(MAX_N); i++){ if( arr[i] ){ se.insert(i); } } return ; } signed main(void){ int N; cin >> N; set> ans; eratosthenes(); division[1] = 1; int left = max(N/2 - (int)sqrt(N) - 10,1LL); int right = min(N/2 + (int)sqrt(N) + 10,N ); for(int i = left; i <= right; i++){ // iの約数の個数を計算しておく // N/2の√N周りらへんを計算しておけば十分そう(予想) int res = i; int s = 1LL; if( arr[res] ){ division[i] = 2; continue;} // p と 1 for(auto d : se){ if(res % d == 0 ){ int cnt = 1LL; while( res % d == 0 ){ res /= d; cnt++; } s *= cnt; if( res == 1 ){ break;} //for-脱出 }// if res%d }//for-d if( arr[res] ){ s *= 2;} division[i] = s; } int rem = inf; for(int A = left; A <= right; A++){ int B = N-A; if( A <= 0 || B <= 0 ){ continue;} int FA = A-division[A]; int FB = B-division[B]; if( rem > abs(FA-FB) ){ rem = abs(FA-FB); ans.clear(); ans.insert({A,B}); } else if( rem == abs(FA-FB) ){ ans.insert({A,B}); } } for(auto ne : ans ){ cout << ne.first << " " << ne.second << endl;} return 0; }