import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); String line = null; while (cin.hasNext()) { line = cin.nextLine(); } cin.close(); divided(Long.parseLong(line)); } private static void divided(long n) { long maxSlice = n - 1; long minSlice; /* nが素数か判定する */ boolean isPrime = new BigInteger(String.valueOf(n)).isProbablePrime(8); if (isPrime) { minSlice = n - 1; } else { double thirdRoot = Math.cbrt(n); if (thirdRoot == (long) thirdRoot) { /* たまたまNが整数の3乗だった場合は、(thirdRoot-1)*3が答え */ minSlice = ((long) thirdRoot - 1) * 3; } else { /* 3乗根が整数にならないのであれば、それより大きい値から順に割っていき、3乗根以上でもっとも小さい約数を求める */ long divisorOverThirdRoot = n; for (long i = (long) thirdRoot + 1; i < n; i++) { if (n % i == 0) { divisorOverThirdRoot = i; break; } } long rest = n / divisorOverThirdRoot; /* 割った残りの値が素数かを判定する */ boolean isPrimeOfRest = new BigInteger(String.valueOf(rest)).isProbablePrime(8); if (isPrimeOfRest) { /* 残りの数が素数なのであれば、約数側がさらに2数の積にならないかを確認する */ boolean isPrimeOfDivisor = new BigInteger(String.valueOf(divisorOverThirdRoot)).isProbablePrime(8); if (isPrimeOfDivisor) { /* Nが素数×素数の形になってしまった場合、それ以上の分割は無理 */ minSlice = (divisorOverThirdRoot - 1) + (rest - 1); } else { /* 約数側をさらに2数の積で分割する。約数の平方根をとる */ double rootOfDivisor = Math.sqrt(divisorOverThirdRoot); if (rootOfDivisor == (long) rootOfDivisor) { /* 平方根が整数だった場合は、(root-1)*2に(rest-1)を足したものが答え */ minSlice = ((long) rootOfDivisor - 1) * 2 + (rest - 1); } else { long divisorOverRoot = divisorOverThirdRoot; for (long i = (long) rootOfDivisor + 1; i < divisorOverThirdRoot; i++) { if (divisorOverThirdRoot % i == 0) { divisorOverRoot = i; break; } } long result = divisorOverThirdRoot / divisorOverRoot; minSlice = (rest - 1) + (divisorOverRoot - 1) + (result - 1); } } } else { /* 残った数が素数でないなら、そちらをさらに2数の積の形にする。 */ double rootOfRest = Math.sqrt(rest); if (rootOfRest == (long) rootOfRest) { minSlice = ((long) rootOfRest - 1) * 2 + (divisorOverThirdRoot - 1); } else { long divisorOfRoot = rest; for (long i = (long) rootOfRest + 1; i < rest; i++) { if (rest % i == 0) { divisorOfRoot = i; break; } } long result = rest / divisorOfRoot; minSlice = (divisorOfRoot - 1) + (result - 1) + (divisorOverThirdRoot - 1); } } } } System.out.println(minSlice + " " + maxSlice); } }