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 - 1; /* nが素数か判定する */ boolean isPrime = new BigInteger(String.valueOf(n)).isProbablePrime(15); if (isPrime) { minSlice = n - 1; } else { double thirdRoot = Math.sqrt(n); System.out.println("thirdRoot=" + thirdRoot); /* 3乗根が整数にならないのであれば、それより小さい値から順に割っていき、3乗根以下でもっとも大きい約数を求める */ long divisorUnderThirdRoot = n; for (long i = (long) thirdRoot; i > 1; i--) { if (n % i == 0) { divisorUnderThirdRoot = i; long rest = n / divisorUnderThirdRoot; /* 割った残りの値が素数かを判定する */ boolean isPrimeOfRest = new BigInteger(String.valueOf(rest)).isProbablePrime(8); if (isPrimeOfRest) { /* 残りの数が素数なのであれば、約数側がさらに2数の積にならないかを確認する */ boolean isPrimeOfDivisor = new BigInteger(String.valueOf(divisorUnderThirdRoot)).isProbablePrime(8); if (isPrimeOfDivisor) { /* Nが素数×素数の形になってしまった場合、それ以上の分割は無理 */ minSlice = (divisorUnderThirdRoot - 1) + (rest - 1); break; } else { /* 約数側をさらに2数の積で分割する。約数の平方根をとる */ double rootOfDivisor = Math.sqrt(divisorUnderThirdRoot); if (rootOfDivisor == (long) rootOfDivisor) { /* 平方根が整数だった場合は、(root-1)*2に(rest-1)を足したものが答え */ minSlice = ((long) rootOfDivisor - 1) * 2 + (rest - 1); break; } else { long divisorOverRoot = divisorUnderThirdRoot; for (long j = (long) rootOfDivisor; j > 1; j--) { if (divisorUnderThirdRoot % j == 0) { divisorOverRoot = j; break; } } long result = divisorUnderThirdRoot / divisorOverRoot; minSlice = (rest - 1) + (divisorOverRoot - 1) + (result - 1); break; } } } else { /* 残った数が素数でないなら、そちらをさらに2数の積の形にする。 */ double rootOfRest = Math.sqrt(rest); long tempMinSlice; if (rootOfRest == (long) rootOfRest) { tempMinSlice = ((long) rootOfRest - 1) * 2 + (divisorUnderThirdRoot - 1); } else { long divisorOfRoot = rest; for (long j = (long) rootOfRest; j > 1; j--) { if (rest % j == 0) { divisorOfRoot = j; break; } } long result = rest / divisorOfRoot; tempMinSlice = (divisorOfRoot - 1) + (result - 1) + (divisorUnderThirdRoot - 1); } if (tempMinSlice < minSlice) { minSlice = tempMinSlice; } } } } } System.out.println(minSlice + " " + maxSlice); } }