AtCoder Beginner Contest 144 - Walk on Multiplication Table

Takahashi is standing on a multiplication table with infinitely many rows and columns.
The square (i,j) contains the integer i \times j. Initially, Takahashi is standing at (1,1).
In one move, he can move from (i,j) to either (i+1,j) or (i,j+1).
Given an integer N, find the minimum number of moves needed to reach a square that contains N.

-----Constraints-----
 - 2 \leq N \leq 10^{12}
 - N is an integer.

-----Input-----
Input is given from Standard Input in the following format:
N

-----Output-----
Print the minimum number of moves needed to reach a square that contains the integer N.

-----Sample Input-----
10

-----Sample Output-----
5

(2,5) can be reached in five moves. We cannot reach a square that contains 10 in less than five moves.

Difficulty: EASY

Starter code:

Solutions:
n = int(input())
a = n + 1
for i in range(1, int(n ** 0.5) + 3):
	if n % i == 0:
		a = min(a, i + n // i)
print(a - 2)


def main():
	N = int(input())
	candidate = []
	for divisor in range(1, int(N ** 0.5) + 1):
		if N % divisor == 0:
			candidate.append((divisor, N // divisor))
	ans = min([a + b - 2 for (a, b) in candidate])
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = 10 ** 18
for i in range(1, int(n ** 0.5) + 2):
	if n % i < 1:
		a = min(a, n // i + i - 2)
print(a)


n = int(input())
for i in range(int(n ** 0.5), 0, -1):
	if n % i == 0:
		print(i + n // i - 2)
		exit()


n = int(input())
(x, y) = (1, n)
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		x = i
y = n // x
print(x + y - 2)


n = int(input())
print(min((x + n // x - 2 for x in range(1, int(n ** 0.5) + 1) if n % x < 1)))


N = int(input())
a = 0
for i in range(1, int(N ** (1 / 2) + 1)):
	b = N // i
	if N % i == 0:
		a = i + b - 2
print(int(a))


a = int(input())
b = int(a ** (1 / 2))
m = a
for i in range(2, b + 1):
	if a % i == 0:
		m = i
c = a / m
print(int(m + c - 2))


import math
n = int(input())
t = int(math.sqrt(n))
while n % t != 0:
	t -= 1
a = t
b = n // a
print(str(a + b - 2))


N = int(input())
print(min((N // i + i - 2 for i in range(1, int(N ** 0.5) + 1) if N % i == 0)))


n = int(input())
r = round(n ** 0.5)
while n % r > 0:
	r = r - 1
print(r + int(n / r) - 2)


def make_divisors(n):
	(lower_divisors, upper_divisors) = ([], [])
	i = 1
	while i * i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n // i)
		i += 1
	return lower_divisors + upper_divisors[::-1]
N = int(input())
A = make_divisors(N)
ans = pow(10, 15)
for x in A:
	temp = N // x + x
	ans = min(ans, temp)
print(ans - 2)


n = int(input())
i = 1
a = 1
while i * i <= n:
	if n % i == 0:
		a = i
	i += 1
b = n // a
print(a + b - 2)


N = int(input())
m = 10 ** 12
for i in range(1, 10 ** 6 + 1):
	if N % i == 0:
		m = min(m, i + N // i)
print(m - 2)


n = int(input())
i = 1
while i * i <= n:
	if n % i == 0:
		x = i
		y = n // i
	i += 1
print(x + y - 2)


n = int(input())
x = int(n ** 0.5)
while n % x != 0:
	x -= 1
print(n // x + x - 2)


import math
N = int(input())
min_cost = N - 1
for i in range(1, int(math.sqrt(N)) + 1):
	tmp = 0
	if N % i == 0:
		tmp = i - 1 + (N / i - 1)
		if tmp < min_cost:
			min_cost = tmp
print(int(min_cost))


n = int(input())
c = max([i for i in range(1, int(n ** 0.5 + 1)) if n % i == 0])
print(c + n // c - 2)


N = int(input())
ans = N - 1
x = 1
while x * x <= N:
	if N % x == 0:
		y = N // x
		ans = min(x - 1 + y - 1, ans)
	x += 1
print(ans)


n = int(input())
import math
a = math.floor(math.sqrt(n))
while a > 0:
	if n % a == 0:
		break
	a -= 1
print(a - 2 + n // a)


n = int(input())
for c in range(int(n ** 0.5), 0, -1):
	if n % c == 0:
		d = int(n / c)
		break
print(c + d - 2)


n = int(input())
c = n - 1
for i in range(1, int(n ** 0.5) + 1):
	if (n / i).is_integer():
		j = n // i
		c = min(c, i + j - 2)
print(c)


N = int(input())
cnt = 10 ** 12
for i in range(1, int(N ** 0.5) + 1):
	if N % i == 0:
		cnt = min(cnt, i + N // i - 2)
print(cnt)


n = int(input())
f = 1
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		f = i
print(f - 1 + n // f - 1)


import math
N = int(input())
ans = N - 1
for i in range(1, int(math.sqrt(N)) + 1):
	if N % i == 0:
		ans = min(ans, N // i + i - 2)
print(ans)


n = int(input())
ans = 10 ** 12
for a in range(1, 10 ** 6 + 1):
	if n % a == 0:
		b = n // a
	ans = min(ans, a + b - 2)
print(ans)


n = int(input())
i = int(n ** (1 / 2))
while n % i:
	i -= 1
j = n // i
ans = i - 1 + (j - 1)
print(ans)


n = int(input())
m = float('inf')
for i in range(1, 1000001):
	if n % i == 0:
		m = min(m, n // i + i - 2)
print(m)


N = int(input())
check = 1
while check ** 2 <= N:
	if N % check == 0:
		keep = N // check
	check += 1
print(keep + N // keep - 2)


N = int(input())
for i in range(int(N ** 0.5), 0, -1):
	if N % i == 0:
		print(i - 1 + N // i - 1)
		break


import math
n = int(input())
ans = float('inf')
for i in range(1, int(math.sqrt(n)) + 1):
	if n % i == 0:
		ans = min(ans, i + n // i - 2)
print(ans)


n = int(input())
ans = 10 ** 18
for i in range(1, 10 ** 6 + 1):
	if n % i == 0:
		j = n // i
	ans = min(ans, i + j - 2)
print(ans)


import math
n = int(input())
a = 1
for i in reversed(list(range(1, int(math.sqrt(n)) + 1))):
	if n % i == 0:
		a = i
		break
print(a + int(n // a) - 2)


n = int(input())
p = int(n ** (1 / 2))
while n % p != 0:
	p -= 1
print(int(p + n / p - 2))


import math
n = int(input())
m = math.floor(n ** 0.5)
while n % m != 0:
	m -= 1
print(m + n // m - 2)


import math
n = int(input())
(a, b) = (1, n)
for i in range(1, int(math.sqrt(n) + 1)):
	if n % i == 0:
		q = n // i
		if abs(a - b) > abs(q - i):
			(a, b) = (i, q)
print(a - 1 + (b - 1))


n = int(input())
x = 10 ** 13
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		x = min(x, n // i + i - 2)
print(x)


import math
n = int(input())
List = []
n_sqrt = int(math.sqrt(n))
for i in range(1, n_sqrt + 1):
	if n % i == 0:
		number = i + n // i - 2
		List.append(number)
print(min(List))


n = int(input())
k = []
for i in range(int(n ** 0.5)):
	if n % (i + 1) == 0:
		k.append(int(i - 1 + n / (i + 1)))
print(min(k))


n = int(input())
a = int(n ** 0.5)
while n % a != 0:
	a = a - 1
else:
	print(a + n // a - 2)


n = int(input())
ans = float('inf')
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		j = n // i
		ans = min(ans, i - 1 + j - 1)
print(ans)


n = int(input())
ans = float('inf')
for i in range(1, int(n ** 0.5) + 1):
	if i * (n // i) == n:
		ans = min(ans, abs(i + n // i) - 2)
print(ans)


from math import sqrt
n = int(input())
i = int(sqrt(n) + 1)
while n % i > 0:
	i -= 1
j = n // i
ans = i + j - 2
print(ans)


n = int(input())
val = int(n ** 0.5)
while n % val != 0:
	val -= 1
print(val + n // val - 2)


N = int(input())
i = int(N ** 0.5)
while N % i:
	i -= 1
print(i + N // i - 2)


N = int(input())
print(min([sum([i - 1, round(N / i) - 1]) for i in range(1, int(N ** 0.5) + 1) if N % i == 0]))


n = int(input())
ans = 1001001001001
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		ans = min(ans, i + n // i - 2)
print(ans)


n = int(input())
move = int(n ** 0.5)
while n % move != 0:
	move -= 1
print(n // move + move - 2)


n = int(input())
i = 1
ans = n - 1
while i * i <= n:
	if n % i == 0:
		ans = i + n / i - 2
	i = i + 1
ans = int(ans)
print(ans)


import math
N = int(input())
ans = 10 ** 12
for i in range(1, math.ceil(math.sqrt(N)) + 2):
	if N % i == 0:
		tem = N // i + N // (N // i) - 2
		if tem <= ans:
			ans = tem
print(ans)


tall = int(input())
bit = int(tall ** (1 / 2))
while tall / bit % 1 != 0:
	bit -= 1
print(int(bit + tall / bit - 2))


n = int(input())
i = 1
ans = 10 ** 13
while i * i <= n:
	if n % i == 0:
		ans = min(ans, n // i + i - 2)
	i += 1
print(ans)


n = int(input())
ans = float('inf')
for a in range(1, int(n ** 0.5 + 1)):
	if n % a == 0:
		ans = min(ans, a + n // a - 2)
print(ans)


n = int(input())
r = 10 ** 12
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		r = min(r, i + n // i - 2)
print(r)


def divisor(n):
	i = 1
	table = []
	while i * i <= n:
		if n % i == 0:
			table.append(i)
			table.append(n // i)
		i += 1
	table = list(set(table))
	return table

def resolve():
	n = int(input())
	ans = float('inf')
	c = divisor(n)
	for a in c:
		b = n // a
		ans = min(ans, a + b - 2)
	print(ans)
resolve()


n = int(input())
a = n - 1
for i in range(1, int(n ** 0.5) + 1):
	if n % i:
		continue
	(j, k) = (i, n // i)
	a = min(a, j + k - 2)
print(a)


n = int(input())
end = int(n ** (1 / 2))
for i in range(end, 0, -1):
	if n % i == 0:
		j = n // i
		print(i + j - 2)
		break


import math
N = int(input())
a = int(math.sqrt(N))
while N % a != 0:
	a -= 1
b = N // a
print(a + b - 2)


N = int(input())
ans = 10 ** 12
for i in range(1, int(N ** 0.5) + 1):
	j = N / i
	if j == int(j):
		ans = i + j - 2
print(int(ans))


import math
n = int(input())
r = int(math.sqrt(n))
while n % r != 0:
	r -= 1
print(n // r + r - 2)


n = int(input())
ans = 10 ** 50
for i in range(1, int(n ** 0.5) + 2):
	if n % i == 0:
		m = i + n // i - 2
		ans = min(ans, m)
print(ans)


def make_divisors(n):
	(lower_divisors, upper_divisors) = ([], [])
	i = 1
	while i * i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n // i)
		i += 1
	return lower_divisors + upper_divisors[::-1]
N = int(input())
yakusu_list = make_divisors(N)
if len(yakusu_list) % 2 == 1:
	ans = (yakusu_list[len(yakusu_list) // 2] - 1) * 2
else:
	ans = yakusu_list[len(yakusu_list) // 2 - 1] - 1 + yakusu_list[len(yakusu_list) // 2] - 1
print(ans)


N = int(input())
a = 1
while a * a <= N:
	if N % a == 0:
		k = a
	a += 1
b = N // k
print(b + k - 2)


import math
n = int(input())
for i in range(int(math.sqrt(n)), 0, -1):
	if n % i == 0:
		print(int(i + n / i - 2))
		break


N = int(input())
i1 = round(N ** 0.5)
while True:
	if N % i1 == 0:
		break
	i1 -= 1
print(i1 + round(N / i1) - 2)


N = int(input())
M = int(N ** (1 / 2) + 1)
s = 0
for i in range(M, 0, -1):
	if N % i == 0:
		s = i
		break
print(int(s + N / s - 2))


N = int(input())
answer = 1000000000000
for i in range(1, int(N ** 0.5) + 2):
	if N % i == 0:
		j = N // i
		if i + j - 2 < answer:
			answer = i + j - 2
print(answer)


N = int(input())
K = int(N ** 0.5)
for i in range(1, K + 1):
	if N % i == 0:
		a = i
		b = N // a
print(a - 1 + b - 1)


N = int(input())

def low_divisors(N):
	K = 1
	low_divs = []
	while K * K <= N:
		if N % K == 0:
			low_divs.append(K)
		K += 1
	return low_divs
L_divs = low_divisors(N)
D = []
for i in range(len(L_divs)):
	D.append(L_divs[i] + N // L_divs[i])
print(min(D) - 2)


N = int(input())
ans = N * 2 - 2
for n in range(1, int(N ** 0.5) + 1):
	if N % n == 0:
		ans = min(ans, N // n + n - 2)
print(ans)


N = int(input())
import math
K = math.sqrt(N)
K = round(K)
for i in range(K):
	L = N // K
	if N == L * K:
		break
	else:
		K -= 1
ans = K + L
ans -= 2
print(ans)


n = int(input())
a = 1
for i in range(1, int(n ** (1 / 2) + 2)):
	if n % i == 0:
		a = max(a, i)
print(int(a + n / a - 2))


n = int(input())
ans = float('inf')
a = 1
while n ** 0.5 >= a:
	if n % a == 0:
		ans = min(ans, a + n // a - 2)
	a += 1
print(ans)


N = int(input())
n = int(N ** 0.5)
for i in range(n):
	i = n - i
	if N % i == 0:
		print(N // i + i - 2)
		break


import math
N = int(input())
a = int(math.sqrt(N))
while a > 0:
	if N % a == 0:
		print(a + N // a - 2)
		break
	a -= 1


N = int(input())
for k in range(int(N ** 0.5), 0, -1):
	if N % k == 0:
		print(k + N // k - 2)
		break


N = int(input())
S = []
for i in range(1, int(N ** (1 / 2)) + 1):
	if N % i == 0:
		S.append(i + N // i - 2)
print(min(S))


num = int(input())
print(min((i + num // i - 2 for i in range(1, int(num ** (1 / 2)) + 1) if not num % i)))


a = int(input())
i = 1
while i <= a // i:
	i += 1
while a % i != 0:
	i -= 1
print(i + a // i - 2)


import math
N = int(input())
result = [10 ** 13]
cnt = []
for i in range(1, int(math.sqrt(N)) + 1):
	if N % i == 0:
		buf = min(result[-1], i + N // i)
		result.append(buf)
		if result[-1] != result[-2]:
			cnt.append([i, N // i])
print(cnt[-1][0] - 1 + cnt[-1][1] - 1)


n = int(input())
a = int(n ** (1 / 2))
while True:
	if n % a == 0:
		print(a - 1 + n // a - 1)
		return
	a -= 1


a = input()
a = int(a)
c = 1
b = round(a ** 0.5) + 2
for n in range(1, b):
	if a % n == 0:
		c = n
d = a / c
print(int(d + c - 2))


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
INF = float('inf')
(YES, Yes, yes, NO, No, no) = ('YES', 'Yes', 'yes', 'NO', 'No', 'no')
(dy4, dx4) = ([0, 1, 0, -1], [1, 0, -1, 0])
(dy8, dx8) = ([0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1])

def inside(y, x, H, W):
	return 0 <= y < H and 0 <= x < W

def ceil(a, b):
	return (a + b - 1) // b

def sum_of_arithmetic_progression(s, d, n):
	return n * (2 * s + (n - 1) * d) // 2

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	g = gcd(a, b)
	return a / g * b

def solve():
	N = int(input())
	ans = INF
	for i in range(1, int(sqrt(N)) + 10):
		j = N // i
		if i * j == N:
			ans = min(ans, i + j - 2)
	print(ans)

def main():
	solve()

def __starting_point():
	main()
__starting_point()


N = int(input())
x = int(N ** 0.5) + 1
ans_1 = N
for i in range(x):
	if N % x == 0:
		ans_1 = x
		break
	else:
		x -= 1
ans_2 = N // ans_1
print(ans_1 + ans_2 - 2)


def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def main():
	N = int(input())
	d = make_divisors(N)
	d.reverse()
	ans = float('inf')
	for i in range(N):
		if len(d) == 1:
			a = d.pop()
			ans = min(ans, 2 * (a - 1))
			break
		if len(d) == 0:
			break
		a = d.pop() - 1
		b = d.pop() - 1
		ans = min(ans, a + b)
	print(ans)

def __starting_point():
	main()
__starting_point()


import math
N = int(input())
p = math.floor(math.sqrt(N))
while N % p > 0:
	p -= 1
q = N // p
print(p + q - 2)


A = int(input())
K = int(A ** 0.5)
for i in range(K):
	j = K - i
	if A % j == 0:
		break
print(j + A // j - 2)


N = int(input())
A = int(N ** (1 / 2))
for i in range(N):
	if N % (A - i) == 0:
		print(int(A - i + N / (A - i) - 2))
		break


N = int(input())
for i in reversed(range(1, int(N ** 0.5) + 1)):
	if N % i == 0:
		print(N // i - 1 + i - 1)
		exit()


import math
N = int(input())
N_ = int(math.sqrt(N)) + 1
min_distance = N - 1
for i in range(1, N_):
	(p, r) = divmod(N, i)
	if r == 0:
		if 1 <= p <= N:
			distance = i - 1 + (p - 1)
			min_distance = min(min_distance, distance)
		else:
			continue
print(min_distance)


n = int(input())
i = int(n ** (1 / 2))
while i >= 2:
	if n % i == 0:
		break
	i -= 1
print(i + n // i - 2)


import math
N = int(input())
x = int(math.sqrt(N))
while N % x != 0:
	x -= 1
print(x - 1 + (N // x - 1))


n = int(input())
for a in range(1, int(n ** 0.5) + 1):
	if n % a == 0:
		ans = a + n // a - 2
print(ans)


n = int(input())
m = 10 ** 13
for x in range(1, 1000001):
	y = n / x
	if y % 1 == 0:
		v = x + y - 2
		m = min(m, v)
print(int(m))


n = int(input())
import math
m = int(math.sqrt(n))
while n % m != 0:
	m -= 1
else:
	print(int(m + n / m - 2))


n = int(input())
k = int(n ** 0.5)
while n % k != 0:
	k -= 1
print(k - 1 + (n // k - 1))


n = int(input())
import math
t = math.ceil(math.sqrt(n))
for i in range(t, 1, -1):
	if n % i == 0:
		print(i - 1 + n // i - 1)
		break
else:
	print(n - 1)


import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
input = sys.stdin.readline

def RD():
	return input().rstrip()

def F():
	return float(input().rstrip())

def I():
	return int(input().rstrip())

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def LI():
	return list(map(int, input().split()))

def TI():
	return tuple(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def Init(H, W, num):
	return [[num for i in range(W)] for j in range(H)]

def main():
	N = I()
	num = math.ceil(math.sqrt(N))
	ans = float('inf')
	for a in range(1, num + 1):
		if N % a == 0:
			b = N // a
			ans = min(ans, a + b - 2)
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
ans = 10000000000000
for i in range(1, int(n ** 0.5) + 1):
	if n % i != 0:
		continue
	j = n // i
	ans = min(ans, i - 1 + (j - 1))
print(ans)


n = int(input())
ans = n
cnt = 0
for i in range(2, int(n ** 0.5) + 2):
	if n % i == 0:
		cnt += 1
		if ans > i + n / i - 2:
			ans = i + n / i - 2
if cnt == 0:
	ans = n - 1
print(int(ans))


import math
N = int(input())
n = int(math.ceil(math.sqrt(N)))
ans = int(1e+18)
for i in range(1, n + 1):
	j = N // i
	if N % i == 0:
		ans = min(ans, j + i - 2)
print(ans)


n = int(input())
x = int(n ** 0.5)
while n % x != 0:
	x -= 1
(x, y) = (x - 1, n // x - 1)
print(x + y)


import math
a = int(input())
b = 1
for i in range(1, math.ceil(a ** 0.5) + 1):
	if a % i == 0:
		b = i
print(b + a // b - 2)


n = int(input())
x = 1
mn = n - 1
while x ** 2 <= n:
	if n % x == 0:
		y = n // x
		mn = min(mn, x + y - 2)
	x += 1
print(mn)


from math import sqrt as s
N = int(input())
(x, y) = ([], [])
for i in range(1, int(s(N)) + 1):
	if N % i == 0:
		x.append(i)
		y.append(N // i)
(ans, M) = (float('INF'), len(x))
for i in range(M):
	ans = min(ans, x[i] + y[i] - 2)
print(ans)


from math import sqrt

def main():
	N = int(input())
	ans = 1000000000000.0 + 1
	for i in range(1, int(sqrt(N)) + 1):
		if N % i == 0:
			j = N // i
			ans = min(ans, i + j - 2)
	print(ans)

def __starting_point():
	main()
__starting_point()


N = int(input())
yakusu = []
for i in range(1, int(N ** 0.5 + 1)):
	if N % i == 0:
		j = int(N / i)
		yakusu.append([i, j])
min_dis = 1000000000000000000000000000000000000000000000000000
for k in range(len(yakusu)):
	distance = yakusu[k][0] - 1 + yakusu[k][1] - 1
	if distance < min_dis:
		min_dis = distance
print(min_dis)


n = int(input())
qa = [n + 1]
for i in range(1, int(n ** (1 / 2)) + 1):
	if n % i == 0:
		qa.append(i - 1 + n // i - 1)
print(min(qa))


import sys
n = int(input())
c = []
for i in range(2, int(n ** (1 / 2)) + 1):
	if n % i == 0:
		c.append(i + n // i - 2)
if len(c) == 0:
	print(n - 1)
	return
print(min(c))


n = int(input())
k = 1
ans = n - 1
while k * k <= n:
	if n % k == 0:
		r = n // k
		ans = min(ans, k + r - 2)
	k += 1
print(ans)


n = int(input())
for i in range(-int(-n ** 0.5 // 1), 0, -1):
	if n % i == 0:
		a = i
		b = n // i
		break
print(a + b - 2)


N = int(input())
ans = N * 2
i = 1
while i * i <= N:
	if N % i == 0:
		ans = min(ans, N // i + i)
	i += 1
print(ans - 2)


N = int(input())
N_ri = round(pow(N, 1 / 2))
for i in range(N_ri, 0, -1):
	if N % i == 0:
		j = N // i
		break
print(i + j - 2)


a = int(input())
r = int(a ** (1 / 2))
k = r
while a % k != 0:
	k -= 1
ans = k + a // k - 2
print(ans)


N = int(input())
for i in range(1, int(N ** (1 / 2)) + 1):
	if N % i == 0:
		MAX = i
ans = MAX + N // MAX - 2
print(ans)


n = int(input())
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		p = i
q = n // p
print(p + q - 2)


n = int(input())
ans = n - 1
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		ans = min(ans, i + n // i - 2)
	else:
		continue
print(ans)


import math
n = int(input())

def p(x):
	if x == 2:
		return True
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			return False
	return True

def check(x):
	res = 10 ** 12
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			s = i - 1 + (x // i - 1)
			res = min(res, s)
	return res
if p(n):
	print(n - 1)
else:
	print(check(n))


n = int(input())
tmp = 1
for i in range(1, round(n ** 0.5) + 1):
	if n % i == 0:
		tmp = i
print(tmp + n // tmp - 2)


import math
n = int(input())
(x, y) = (n, 1)
for i in range(int(math.sqrt(n)), 0, -1):
	if n % i == 0:
		if x + y > i + n // i:
			x = i
			y = n // x
print(x - 1 + y - 1)


N = int(input())
n = int(N ** (1 / 2))
for i in range(n, 0, -1):
	if N % i == 0:
		b = N // i
		print(i + b - 2)
		break


a = int(input())
for x in range(int(a ** 0.5), 0, -1):
	if a % x == 0:
		b = int(a // x)
		break
print(b + x - 2)


import math
N = int(input())
a = 0
for i in range(1, int(math.sqrt(N) // 1) + 1):
	a = max(a, math.gcd(N, i))
print(a + N // a - 2)


n = int(input())
for i in list(range(1, int(n ** 0.5) + 1))[::-1]:
	if n % i == 0:
		ans = i + n // i
		break
print(ans - 2)


def divisor(n):
	i = 1
	table = []
	while i * i <= n:
		if n % i == 0:
			table.append([i, n // i])
		i += 1
	return table
N = int(input())
m = N
if len(divisor(N)) == 1:
	print(N - 1)
else:
	for (i, j) in divisor(N):
		m = min(m, i + j)
	print(m - 2)


n = int(input())
l = [n / i + i - 2 for i in range(1, int(n ** 0.5) + 1) if n % i == 0]
print(int(min(l)))


a = int(input())
k = int(a ** 0.5)
while a % k:
	k -= 1
print(k + a // k - 2)


n = int(input())
l = set()
for i in range(1, int(n ** (1 / 2)) + 1):
	if n % i == 0:
		l.add(n // i + i)
print(min(list(l)) - 2)


import math
n = int(input())
top = int(math.sqrt(n))
a = 1
for x in range(1, top + 1):
	if n % x == 0:
		a = x
a_pair = n // a
print(a + a_pair - 2)


import math
n = int(input())
l = math.floor(math.sqrt(n))
for i in range(1, l + 1):
	if n % i == 0:
		x = i
		y = n // i
print(x - 1 + (y - 1)) if x > 0 else print(n - 1)


N = int(input())
num = set()
for n in range(2, 10 ** 7):
	if N % n == 0:
		num.add(tuple(sorted([n, N // n])))
	if N == n:
		break
ans = (10 ** 12, 10 ** 12)
if not num:
	print(N - 1)
else:
	for s in num:
		if s[0] + s[1] < ans[0] + ans[1]:
			ans = s
	print(ans[0] + ans[1] - 2)


N = int(input())
n = round(N ** (1 / 2))
for i in range(1, n + 2):
	if N / i == N // i:
		ans = i + N / i - 2
print(int(ans))


n = int(input())
l = int(n ** 0.5)
while l:
	if n % l:
		l -= 1
	else:
		break
print(l - 1 + (n // l - 1))


n = int(input())
i = int(n ** 0.5)
while n % i:
	i -= 1
print(i + n // i - 2)


n = int(input())
check = 1
while check ** 2 <= n:
	if n % check == 0:
		keep = n // check
	check += 1
print(keep + n // keep - 2)


N = int(input())
s = 0
for i in range(1, round(N ** 0.5) + 1):
	if N % i == 0:
		s = i
print(s + N // s - 2)


import math
N = int(input())
M = []
sqr_N = math.floor(math.sqrt(N))
a = 0
for i in range(1, sqr_N + 1):
	if N % i == 0:
		a = i
a_pair = N // a
print(a + a_pair - 2)


n = int(input())
ans = n - 1
for i in range(2, n):
	j = n // i
	if j < i:
		break
	if n % i:
		continue
	ans = j + i - 2
print(ans)


def enum_divisors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
	return res
N = int(input())
divs = enum_divisors(N)
ans = float('inf')
for d in divs:
	ans = min(ans, d - 1 + (N // d - 1))
print(ans)


n = int(input())
ans = float('inf')
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		t = n // i
		if i - 1 + t - 1 < ans:
			ans = i - 1 + t - 1
print(ans)


import math
n = int(input())
q = math.floor(n ** 0.5)
z = q + 1
while n % z != 0:
	z -= 1
ee = n / z
print(int(ee + z - 2))


n = int(input())
a = int(n ** 0.5)
while n % a != 0:
	a -= 1
b = n // a
print(a + b - 2)


import math
n = int(input())
root_n = math.floor(math.sqrt(n))
ans = 0
for i in range(1, root_n + 1):
	if n % i == 0:
		ans = i
print(int(ans + n / ans - 2))


n = int(input())
m = 10 ** 12
i = 1
while i * i <= n:
	if n % i == 0:
		t = i + n // i - 2
		m = min(m, t)
	i += 1
print(m)


n = int(input())
ans = int(1e+18)
for i in range(1, n):
	if i * i <= n:
		if n % i == 0:
			j = int(n / i)
			ans = min(ans, i + j - 2)
	else:
		break
print(ans)


import sys
n = int(input())
ans = float('inf')
flag = 0
for i in range(2, int(n ** (1 / 2)) + 1):
	if n % i == 0:
		ans = min(ans, i + n // i - 2)
		flag = 1
if flag:
	print(ans)
else:
	print(n - 1)


def divisor(n):
	(lower, upper) = ([], [])
	i = 1
	while i * i <= n:
		if n % i == 0:
			lower.append(i)
			if i != n // i:
				upper.append(n // i)
		i += 1
	return lower + upper[::-1]
n = int(input())
ans = float('inf')
for d in divisor(n):
	i = n // d
	tmp = i + d - 2
	ans = min(ans, tmp)
print(ans)


import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9 + 7
INF = 10 ** 18
eps = 10 ** (-7)
N = int(input())
divisors = []
for i in range(1, int(N ** 0.5) + 1):
	if N % i == 0:
		divisors.append(i)
		if i != N // i:
			divisors.append(N // i)
divisors.sort()
m = len(divisors)
if m % 2 == 0:
	print(divisors[m // 2] + divisors[m // 2 - 1] - 2)
else:
	print(divisors[m // 2] * 2 - 2)


import sys
input = sys.stdin.readline

def main():
	n = int(input())
	ans = 10 ** 12
	for a in range(1, 10 ** 6 + 1):
		if n % a == 0:
			b = n // a
		ans = min(ans, a + b - 2)
	print(ans)

def __starting_point():
	main()
__starting_point()


import math
n = int(input())
a = math.ceil(math.sqrt(n))
b = max([i for i in range(1, a + 1) if n % i == 0])
print(b + n // b - 2)


import math
N = int(input())
key = int(math.sqrt(N))
ans = 10 ** 12
for i in reversed(range(1, key + 1)):
	if N % i == 0:
		ans = i - 1 + N // i - 1
		break
print(ans)


n = int(input())
a = 1
ans = n
while a * a <= n:
	if n % a == 0:
		ans = min(a + n // a - 2, ans)
	a += 1
print(ans)


N = int(input())
d = 10 ** 20
for a in range(1, int(N ** 0.5) + 1):
	if N % a == 0:
		b = N // a
		c = a + b - 2
		if d > c:
			d = c
print(d)


N = int(input())
n = int(N ** (1 / 2))
for i in range(n):
	x = n - i
	if N / x - int(N / x) == 0:
		print(int(x + N / x - 2))
		exit()


x = int(input())
for i in range(int(x ** 0.5), 0, -1):
	if x % i == 0:
		break
print(i + x // i - 2)


import math
n = int(input())
z = math.floor(math.sqrt(n))
ans = 10 ** 12
for i in range(1, z + 1):
	if n % i == 0:
		m = n // i
		ans = min(ans, m + i - 2)
print(ans)


N = int(input())
n = 1
last = 0
while n ** 2 <= N:
	if N % n == 0:
		last = n
	n += 1
print(last + N // last - 2)


N = int(input())
mini = float('inf')
for i in range(1, 10 ** 6 + 1):
	if N % i == 0:
		mini = min(mini, i + N // i)
print(mini - 2)


n = int(input())
res = []
for i in range(1, int(n ** 0.5) + 1):
	if n % i == 0:
		res.append(i + n // i - 2)
print(min(res))


N = int(input())
P = [1, N]
for i in range(1, int(N ** 0.5) + 1):
	if N % i == 0:
		P = [i, N // i]
print(sum(P) - 2)


N = int(input())
n = int(N ** 0.5)
while N % n != 0:
	n -= 1
print(int(n + N / n - 2))


from math import sqrt
n = int(input())
minSoFar = 10 ** 12 + 1
for a in range(1, int(sqrt(n)) + 1):
	if n % a == 0:
		b = n // a
		minSoFar = min(minSoFar, a + b - 2)
print(minSoFar)


N = int(input())
ans = 10 ** 12 + 1
for a in range(1, int(N ** 0.5 + 2)):
	if N % a == 0:
		a_b = a + N // a - 2
	if ans > a_b:
		ans = a_b
print(int(ans))


n = int(input())
ans = 10 ** 15
for i in range(1, int(n ** 0.5) + 10):
	if n % i == 0:
		ans = min(ans, i + n // i - 2)
print(ans)


N = int(input())
a = int(N ** 0.5)
while N % a != 0:
	a -= 1
print(N // a + a - 2)


import sys

def make_divisors(n):
	(lower_divisors, upper_divisors) = ([], [])
	i = 1
	while i * i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n // i)
		i += 1
	return lower_divisors + upper_divisors[::-1]
input = sys.stdin.readline
n = int(input())
yaku_list = make_divisors(n)
index = int(len(yaku_list) / 2)
if len(yaku_list) % 2 == 0:
	result = yaku_list[index - 1] - 1 + yaku_list[index] - 1
else:
	result = yaku_list[index] - 1 + yaku_list[index] - 1
print(result)


import math
ans = 1000000000000000000
N = int(input())
for i in range(math.ceil(math.sqrt(N + 1000))):
	if i > 0 and N % i == 0:
		ans = min(i + N / i - 2, ans)
print(int(ans))


def div(n):
	(lower_divisors, upper_divisors) = ([], [])
	i = 1
	while i * i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n // i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

def main():
	import functools
	import operator
	import numpy as np
	import itertools
	import math
	lis = [1]
	N = int(input())
	x = div(N)
	A = []
	for i in range(math.ceil(len(x) / 2)):
		A.append(x[i] + x[len(x) - i - 1])
	ans = min(A) - 2
	print(ans)
main()


N = int(input())
move = int(N ** 0.5)
while N % move != 0:
	move -= 1
print(N // move + move - 2)