//include //------------------------------------------ #include using namespace std; //typedef //------------------------------------------ using LL = int64_t; using VL = vector; using VVL = vector; using VS = vector; using PLL = pair; //container util //------------------------------------------ #define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) #define rwhole(f,x,...) ([&](decltype((x)) whole) { return (f)(rbegin(whole), rend(whole), ## __VA_ARGS__); })(x) #define EACH(i,c) for(decltype((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define SORT(c) whole(sort, c) #define RSORT(c) rwhole(sort, c) //constant //-------------------------------------------- constexpr double EPS = 1e-10; constexpr double PI = M_PI; constexpr int MOD = 1000000007; // grid //-------------------------------------------- VL dx = {0, 1, 0, -1}; VL dy = {1, 0, -1, 0}; VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1}; VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1}; //debug //-------------------------------------------- #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; //IO accelerate //-------------------------------------------- struct InitIO { InitIO() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(30); } } init_io; //template //-------------------------------------------- // declaretion template istream& operator >>(istream& is, vector& vec); template ostream& operator <<(ostream& os, const pair& p); template ostream& operator <<(ostream& os, const vector& vec); template ostream& operator <<(ostream& os, const vector>& vv); template vector make_v(size_t a); template auto make_v(size_t a,Ts... ts); template typename enable_if::value==0>::type fill_v(T &t,const V &v); template typename enable_if::value!=0>::type fill_v(T &t,const V &v); // implementation template istream& operator >>(istream& is, vector& vec) { for(T& x: vec) is >> x; return is; } template ostream& operator <<(ostream& os, const pair& p) { os << p.first << "," << p.second; return os; } template ostream& operator <<(ostream& os, const vector& vec) { for(int i=0; i ostream& operator <<(ostream& s, const vector>& vv) { for (int i = 0; i < vv.size(); ++i) { s << vv[i] << endl; } return s; } // 多重vector // auto dp=make_v(4,h,w) みたいに使える template vector make_v(size_t a){return vector(a);} template auto make_v(size_t a,Ts... ts){ return vector(ts...))>(a,make_v(ts...)); } // 多重vectorのためのfill // fill_v(dp,0) みたいに使える template typename enable_if::value==0>::type fill_v(T &t,const V &v){t=v;} template typename enable_if::value!=0>::type fill_v(T &t,const V &v){ for(auto &e:t) fill_v(e,v); } template void chmax(T&a,U b){if(a void chmin(T&a,U b){if(b T gcd(T a, T b) { return b?gcd(b,a%b):a;} template T lcm(T a, T b) { return a/gcd(a,b)*b;} //main code std::vector IsPrime; void sieve(size_t max){ if(max+1 > IsPrime.size()){ // resizeで要素数が減らないように IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保 } IsPrime[0] = false; // 0は素数ではない IsPrime[1] = false; // 1は素数ではない for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる if(IsPrime[i]) // iが素数ならば for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は IsPrime[i*j] = false; // 素数ではない } int main(int argc, char *argv[]) { LL x; cin >> x; sieve(x); VL primes; for (int i = 0; i <= x; i++) { if (IsPrime[i]) { primes.emplace_back(i); } } VL f(x+1); for (int i = 1; i <= x; i++) { int ti = i; LL ta = 1; for (int j = 0; j < primes.size(); j++) { if (ti==1) { break; } if (primes[j]*primes[j] > ti) { ta*=2; break; } int tj = 1; while (ti%primes[j]==0) { ti/=primes[j]; tj++; } ta *= tj; } f[i] = i - ta; } LL mm = INT32_MAX; for (int i = 1; i < x; i++) { chmin(mm, abs(f[i] - f[x-i])); } for (int i = 1; i < x; i++) { if (abs(f[i] - f[x-i]) == mm) { cout << i << " " << x-i << endl; } } return 0; }