Problem:


Score : 300 points

Problem Statement

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 1

10

Sample Output 1

5

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

Sample Input 2

50

Sample Output 2

13

(5, 10) can be reached in 13 moves.

Sample Input 3

10000000019

Sample Output 3

10000000018

Both input and output may be enormous.



Sample input:
10


Sample output:
5

Submission status: Accepted

Solution code:
from math import sqrt
n = int(input())
a = int(sqrt(n))
for i in range(1, a+1):
  if n % i == 0:
    ans = n // i + i - 2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = 10 ** 12 +1
for i in range(n):
  k = i+1
  if n%k == 0:
    ans = min(ans, n//k + k -2)
  if i ** 2 > n:
    break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def divisors(n, sort=False):
    """
    nの約数をO(√n)で列挙する
    """
    d = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d.append(i)
            if i != n // i:
                d.append(n//i)
    if sort:
        d.sort()
    return d


N = int(input())

ans = float('inf')
d = divisors(N, sort=True)
for i in range(len(d)):
    x, y = d[i], d[-i - 1]
    dist = abs(x - 1) + abs(y - 1)
    ans = min(ans, dist)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())


def main():

    end = N ** 0.5
    minv = 10 ** 12
    list = []
    for i in range(1, int(end) + 1):
        if N % i == 0:
            list.append([i, N / i])
    for item in list:
        minv = min(minv, item[0] + item[1] - 2)

    print(int(minv))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc144/tasks/abc144_c
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
import math
from heapq import heappush, heappop, heapify


def main():
    n = int(input())

    v = 1
    while v * v <= n:
        v += 1

    for i in range(v, 0, -1):
        if n % i == 0:
            j = n // i
            print(i + j - 2)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
res = int(1e13)

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

Submission status: Accepted

Solution code:
import math
n = int(input())
k = math.ceil(math.sqrt(n))
l = 1
for i in range(1,k+1):
    if n%i==0:
        l = i
p = n//l
print(p+l-2)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
n = int(input())
ans = 10**18
for a in range(1, n):
    if n%a == 0:
      b = n//a
      ans = min(ans, a+b-2)
    elif a >= n**0.5:
        break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

# print('input >>')
N = int(input())

floorNsqrt = int(math.sqrt(N))

i = 0
while i <= floorNsqrt:
    i += 1
    if N % i == 0:
        N_a = i

N_b = N / N_a
ans = int(N_a-1 + N_b-1)

# print('----------output----------')
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

m = None
for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        j = n // i
        m = min(m, i + j) if m is not None else i + j

print(m - 2)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
# 約数s
def make_divisors(n):
    divisors = []
    ret = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ret.append((i,n//i))
    return ret

if __name__ == "__main__":
    n = int(input())
    ret = make_divisors(n)
    # print(ret)
    ans = 10**18
    for a,b in ret:
        ans = min(a+b, ans)
    print(ans-2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    
    if is_prime(N):
        print(N-1)
        sys.exit()
        
    ll = factorize(N)
    ll.sort()
    
    if len(ll) == 2:
        a = ll[0] -1
        b = ll[1] -1
        print(a + b)
        sys.exit()
        
    tmp = math.sqrt(N)
    max = (tmp // 1) + 1
    ans = INF
    for i in range(1, int(max)):
        b = N / i
        if b.is_integer():
            tmp = (i-1) + (b-1)
            if ans > tmp:
                ans = tmp
                
    print(int(ans))
    
def is_prime(n): 
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True
    
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct
    
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())

U = int(np.sqrt(N)) + 1
div = np.arange(1, U, dtype=np.int64)
div = div[N%div == 0]
div += N//div
print(np.amin(div) - 2)

Submission status: Accepted

Solution code:
import math

N = int(input())
sqrtN = int(math.sqrt(N))

candidate = N - 1

for i in range(2, sqrtN+1):
    if not N % i:
        if N // i + i - 2 < candidate:
            candidate = N // i + i - 2
print(candidate)

Submission status: Accepted

Solution code:
import numpy as np
import math

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

Submission status: Accepted

Solution code:
N = int(input())

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

print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
x = int(math.sqrt(n)) + 1

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

Submission status: Accepted

Solution code:
n = int(input())

ans = n
for i in range(1, n):
	if i * i > n:
		break
	if n%i == 0:
		ans = min(ans, i + n//i - 2)
print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
ans = n-1

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

Submission status: Accepted

Solution code:
import math
n = int(input())
maxn = math.ceil(math.sqrt(n))
res1=1
for i in range(2,maxn+1):
    if n % i == 0:
        res1 = i

print(res1 + (n // res1)-2)

Submission status: Accepted

Solution code:
# C - Walk on Multiplication Table
N = int(input())
for a in range(int(N**.5), 0, -1):
    if N%a == 0: break
print(a + N//a - 2)

Submission status: Accepted

Solution code:
# C - Walk on Multiplication Table
N = int(input())
for a in range(int(N**.5) + 1, 0, -1):
    if N%a == 0: break
print(a + N//a - 2)

Submission status: Accepted

Solution code:
import math

n = int(input())
m = math.floor(math.sqrt(n))
flag = True

while flag:
  if n%m == 0:
    flag = False
    print(m + n//m -2)
  m -= 1

Submission status: Accepted

Solution code:
import math

n=int(input())
r=int(math.sqrt(n))
l=[]
for a in range(1,r+1):
    if n%a == 0:
        l.append(a+int(n/a)-2)
print(min(l))

Submission status: Accepted

Solution code:
#abc144c

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

Submission status: Accepted

Solution code:
import math

N = int(input())
N2 = int(math.sqrt(N))
ans = 0
for i in range(1, N2 + 1):
    j = int(N/i)
    if (i * j == N):
#        print(i,j)
        ans = i + j - 2
#    else:
#        print(i,j)
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())

sqrtN = int(math.sqrt(N))

for i in reversed(range(1, sqrtN+1)):
    if N % i == 0:
        print(int(i + N/i - 2))
        quit(0)

Submission status: Accepted

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

l = len(d)
print(d[l//2 - 1] + d[l//2] - 2)

Submission status: Accepted

Solution code:
import math
import numpy as np
N = int(input())
n = np.arange(1,math.sqrt(N)+1)
print(int(min(np.where(N%n == 0, (N/n)+n-2, np.nan))))

Submission status: Accepted

Solution code:
import math
N = int(input())
max = 0
max2 = 0
for i in range(2, int(math.sqrt(N)+ 2)):
    if N % i == 0:
        max = i
        max2 = N // i
if max != 0:
    print(max + max2 - 2)
else:
    print(N -1)
#print(max, max2)

Submission status: Accepted

Solution code:
import math
N = int(input())
 
lim = int(math.sqrt(N))
 
x = 1
while True:
    if N % lim == 0:
        x = lim
        break
    lim = lim - 1
 
y = N // lim
 
print((x - 1) + (y - 1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
import math


def solve(N: int):
    x = np.arange(1, np.sqrt(N)+1, dtype=np.int)
    div = x[N % x == 0]
    print((N/div + div - 2).min().astype(np.int))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n = int(input())

result = float("INF")
############Optimization###############
start = int(math.sqrt(n)) + 1
for i in range(start, 0, -1):
    if n % i == 0:
        result = i + int(n/i) - 2
        break
print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n=int(input())
m=math.sqrt(n)
m=math.floor(m)
while True:
  if n%m==0:
    print(m+n//m-2)
    break
  else:
    m=m-1

Submission status: Accepted

Solution code:
import math

def sq(n):
    for i in range(math.ceil(math.sqrt(N)), -1, -1):
        if n % i == 0:
            return (i, n//i)

N = int(input())
a, b = sq(N)
print(a + b - 2)

Submission status: Accepted

Solution code:
import math

def sq(n):
    for i in range(math.floor(math.sqrt(N)), 0, -1):
        if n % i == 0:
            return (i, n//i)

N = int(input())
a, b = sq(N)
print(a + b - 2)

Submission status: Accepted

Solution code:
import math
n=int(input())
ans=n+1
i=1
while i<=math.sqrt(n):
    if n%i==0 and ans > i +n/i:
        ans = i + n/i
    i+=1
ans = int(ans)
print(ans-2)

Submission status: Accepted

Solution code:
import math

def sq(n):
    for i in range(math.floor(math.sqrt(N)), -1, -1):
        if n % i == 0:
            return (i, n//i)

N = int(input())
a, b = sq(N)
print(a + b - 2)

Submission status: Accepted

Solution code:
n = int(input())


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

Submission status: Accepted

Solution code:
import math

n=int(input())

root = int(math.sqrt(n))
for i in reversed(range(root+1)):
    if(n%i == 0):
        j=int(n/i)
        print(i+j-2)
        break

Submission status: Accepted

Solution code:
import math
def divisor(x):
    div=[]
    for i in range(1,int(x**(1/2))+1):
        if x%i==0:
            div.append(i)
            if i!=x//i:
                div.append(x//i)
    return sorted(div)

N=int(input())
aa=divisor(N)
bb=[]
for i in range(math.ceil(len(aa)/2)):
    bb.append(aa[i]**2+aa[len(aa)-i-1]**2)
m=bb.index(min(bb))
n=aa[m]-1
r=aa[len(aa)-1-m]-1
print(n+r)

Submission status: Accepted

Solution code:
# ABC144C - Walk on Multiplication Table
def min_div_pairs_sum(x: int) -> int:
    ret = 1 << 60
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            ret = min(ret, i + x // i)
    return ret


def main():
    N = int(input())
    ans = min_div_pairs_sum(N) - 2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC144C - Walk on Multiplication Table
def div_pairs_sum(x: int) -> set:
    divs = set()
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            divs.add(i + x // i)
    return divs


def main():
    N = int(input())
    ans = min(div_pairs_sum(N)) - 2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def divisor(N):
    div = []
    for i in range(1, int(N ** 0.5 + 1)):
        if N % i == 0:
            div.append(i)
            if i * i != N:
                div.append(N // i)
    return sorted(div)


N = int(input())
print(min([d + N // d - 2 for d in divisor(N)]))

Submission status: Accepted

Solution code:
import math
N=int(input())
n=int(math.sqrt(N))
S=0
for i in range(1,n+1):
    if N%i==0:
        s=i+N//i-2
        if S==0:
            S=s
        elif S>=s:
            S=s
print(S)

Submission status: Accepted

Solution code:
n = int(input())
ln = []
for k in range(1,(int(n**0.5))+1):
    if n % k == 0:
        ln.append(k)
if not n**0.5 % 1 == 0:
    for k in reversed(range(0, len(ln))):
        ln.append(n // ln[k])
else:
    for k in reversed(range(0, len(ln)-1)):
        ln.append(n // ln[k])
if not n**0.5 % 1 == 0:
    i = ln[len(ln) // 2 - 1]
    j = ln[len(ln) // 2]
    ans = i + j -2
else:
    ans = int(2*n**0.5)-2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
from collections import Counter
import math
N = int(input())

L = math.sqrt(N)
# print(L)
now = 0
for i in range(1, int(L)+1):
    # print(i)

    if N % i == 0:
        tmp = i + N / i -2
        if now == 0:
            now = tmp
        elif now >= tmp:
            now = tmp
        
        # print(i)
        # print(N/i)
print(int(now))

Submission status: Accepted

Solution code:
n = int(input())
s = []

for i in range(int(n ** (1 / 2))):
    if i > n:
        break
    elif n % (i + 1) == 0:
        j = int(n / (i + 1)) 
        s.append(i + j - 1)

s.sort()                
print(s[0])

Submission status: Accepted

Solution code:
s=[]
n=int(input())
a=int(n**0.5)
for i in range(a):
    if n%(a-i)==0:
        s.append(a-i)
    if len(s)>=1:
        break
b=n//s[0]
print(b+s[0]-2)

Submission status: Accepted

Solution code:
import math
n = int(input())

r = int(math.sqrt(n))

a = 1
b = n

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

Submission status: Accepted

Solution code:
def c_walk_on_multiplication_table():
    N = int(input())
    return min([i + (N // i) - 2 for i in range(1, int(N**0.5) + 1) if N % i == 0])

print(c_walk_on_multiplication_table())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = int(n**(1/2))


for i in range(a):
    if n%(a-i)==0:
        print(n//(a-i)+(a-i)-2)
        break

Submission status: Accepted

Solution code:
n=int(input())
l=1
for i in range(2,int(n**.5)+1):
 if n%i<1:l=i
print(l+n//l-2)

Submission status: Accepted

Solution code:
import math
N=int(input())

A=int(math.sqrt(N))
a=1
b=1
for i in range(1, A+1):
  if N%i==0:
    a=i
    b=N/i
print(int(a+b-2))

Submission status: Accepted

Solution code:
n = int(input())
 
s = list()
for i in range(1, int(n**0.5 + 1)):
    if n % i == 0:
        s.append(int(i + n/i))
print(min(s)-2)

Submission status: Accepted

Solution code:
# C - Walk on Multiplication Table
from math import sqrt
N = int(input())

ans = N
MAX = int(sqrt(N)) + 1
for a in range(1, MAX):
    b = N % a
    if b == 0:
        ans = min(ans, a + N / a - 2)
        
print(int(ans))

Submission status: Accepted

Solution code:
N=int(input())
div=[]

for i in range(1,int(N**0.5)+1):
  if N%i == 0:  
    div.append(i)
    div.append(N/i)

div=list(map(int,div))
div.sort()
num=len(div)//2

x=div[num]
y=div[num-1]

print(x+y-2)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
# coding: utf-8

from math import sqrt
N = int(input())
n = int( N ** 0.5 )
ans = 0


for i in range(1,n+1):
    
    if N % i == 0:
        
      if ans == 0:
        ans = i + N/i
      else:
        ans = min(ans, i + N/i)
        

print(int(ans -2))

Submission status: Accepted

Solution code:
import math

n = int(input())

ans  = 10 ** 12 
for i in range(1, math.floor(math.sqrt(n)) + 1):
    if n%i != 0:
        continue
    j = int(n/i)
    ans = min(ans, i+j-2)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

x=N

import math
xr=math.ceil(math.sqrt(x))

LIST=[]
for i in range(1,xr+1):
    if x%i==0:
        LIST.append(i)
        LIST.append(x//i)

ANS=1<<60

for l in LIST:
    ANS=min(ANS,l-1+N//l-1)

print(ANS)

Submission status: Accepted

Solution code:
A = int(input())
def div(n):
  for i in reversed(range(1, int(n**0.5)+1)):
    if n % i == 0:
      return (i, n//i)
def move(n):
  i, j = div(n)
  return i + j - 2
print(move(A))

Submission status: Accepted

Solution code:
A = int(input())
def getIJ(A):
  for i in reversed(range(1, int(A**0.5)+1)):
    if A % i == 0:
      return (i, A//i)
  return (0, 0)
def calc(A):
  i, j = getIJ(A)
  return i + j - 2
print(calc(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
import math


# ans = 0
n = int(input())
#h = math.ceil(n/2)
dists = []
h = math.ceil(math.sqrt(n))
# i <= jとする
for i in range(1,h + 1):
    if n % i != 0:
      continue
    j = int(n / i)
    dists.append(i + j - 2)
print(min(dists))


# h = math.ceil(n/2)
# board1 = [[0]*h/2 for _ in range(h/2)]
# board2 = [[0]*h/2 for _ in range(h/2)]
# for i in range(1,h/2 + 1):
#   for j in range(1,h/2 + 1):
#     board1[i - 1][j - 1] = i * j
# for i in range(h/2 + 1,h + 1):
#   for j in range(h/2 + 1,h + 1):
#     board2[i - (h/2 + 1)][j - (h/2 + 1)] = i * j
# sx = 1
# sy = 1
# gx = 0
# gy = 0
# dist1 = [[-1]*h/2 for _ in range(h/2)]
# dist2 = [[-1]*h/2 for _ in range(h/2)]
# que = deque([(sy - 1,sx - 1)])
# dist1[sy - 1][sx - 1] = 0
# while que:
#   y,x = que.popleft()
#   if board1[y][x] == n:
#     ans = dist1[y][x]
#     break
#   for y1,x1 in [(y + 1,x),(y, x + 1)]:
#     if y1 < 0 or x1 < 0 or x1 >= h/2:
#       continue
#     if y1 >= h/2:
#       sy = y1
#       sx = x1
#       gy = y
#       gx = x
#       break
#     if dist1[y1][x1] != -1:
#       continue
#     if dist1[y1][x1] == -1:
#       dist1[y1][x1] = dist1[y][x] + 1
#       que.append((y1,x1))
# que = deque([sy,sx])
# dist2[sy][sx] = 0
# while que:
#   y,x = que.popleft()
#   if board2[y][x] == n:
#     ans = dist1[gy][gx] + dist2[y][x]
#     break
#   for y1,x1 in [(y + 1,x),(y, x + 1)]:
#     if y1 < 0 or x1 < 0 or x1 >= h/2:
#       continue
#     if y1 >= h/2:
#       sy = y1
#       sx = x1
#       break
#     if dist2[y1][x1] != -1:
#       continue
#     if dist2[y1][x1] == -1:
#       dist2[y1][x1] = dist2[y][x] + 1
#       que.append((y1,x1))
# print(ans)

Submission status: Accepted

Solution code:
#
# abc144 c
#
import unittest
from io import StringIO
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def resolve():
    N = int(input())

    S = math.ceil(math.sqrt(N))
    ans = N - 1

    for i in range(1, S+1):
        if N % i == 0:
            j = N // i
            ans = min(ans, i+j-2)
    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[: -1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """10"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """50"""
        output = """13"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10000000019"""
        output = """10000000018"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())

ans=pow(10,13)
for i in range(1,int(np.sqrt(N))+1):
    if(N%i!=0):
        continue
    j=N/i
    ans=min(ans,i+j-2)

print(int(ans))

Submission status: Accepted

Solution code:
"""
author : dokueki
"""
import math
n = int(input())
res = []
for i in range(1,int(pow(n,0.5))+1):
    if (n/i)-math.floor(n/i)==0 :
        res.append((i+(n//i))-2)
print(min(res))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

min_cnt = N - 1
for i in range(1, int(N)):
    j = N // i
    if i > j:
        break
    if N % i == 0:
        cnt = (i - 1) + (j - 1)
        if min_cnt > cnt:
            min_cnt = cnt
print(min_cnt)

Submission status: Accepted

Solution code:
import sys
import math
#+++++

def sp(value):
		ret_v=[]
		v=value
		for i in range(2, value):
			if v % i == 0:
				ret_v.append(i)
				v=v//i
				
				while v % i == 0:
					ret_v.append(i)
					v=v//i
					
			if i*i>v:
				ret_v.append(v)
				return (ret_v)
				
		ret_v.append(v)
		return (ret_v)

def main():
	a = int(input())
	mm=a*2
	for i in range(1, int(math.sqrt(a))+1):
		if a % i == 0:
			dd=i+(a//i)-2
			mm=min(dd,mm)

	print(mm)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
N = int(input())
S = N+1
from math import sqrt
for a in range(int(sqrt(N))+2, 0, -1):
    b, y = divmod(N, a)
    if y != 0:
        continue
    S = a + b
    break
print(S-2)

Submission status: Accepted

Solution code:
N = int(input())
n = int((N ** 0.5)//1 + 1)

ans = 1000000
ans_list = []

for i in range(1, n):
    if N % i == 0:
        ans = N / i
        ans_list.append(i + ans)

print(int(min(ans_list)-2))

Submission status: Accepted

Solution code:
import math 
num = int(input())

a = int(math.sqrt(num))
b = num // a

res_list = []

for i in range(1, a+1)[::-1]:
    b = num // i
    if i * b == num:
        print(i + b -2)
        break

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math 
num = int(input())

a = int(math.sqrt(num))
b = num // a

res_list = []
for i in range(1, a +1):
    b = num // i
    if i * b == num:
        res_list.append(i + b -2)

print(min(res_list))

Submission status: Accepted

Solution code:
c=int(input())
count=1
ans=10000000000000
k=c
for i in range(1,int(c**(1/2)+100000)):
    if c%i==0:
        if ans>i+int(c/i):
            ans=i+int(c/i)
        else:
            continue
print(ans-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math 

N = int(input())
lst =[]
#N = a*bとする。　ここで、a<=bが成り立つ。
#√a　の全探索
length= math.ceil(math.sqrt(N))
for i in range(length):
    if(N %(i+1) == 0):
        lst.append(i+1)
a = max(lst)
b = round(N/a)
ans = a+b -2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue
from heapq import heappop, heappush
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

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

Submission status: Accepted

Solution code:
n = int(input())

ans = 0
for i in range(1,n):
    if n % i == 0:
      if ans == 0:
        ans = i + n//i
      else:
        ans = min(ans, i + n//i)
    if i**2 >= n:
      break

print(ans -2)

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
r = int(n ** 0.5)
count = n - 1
for i in range(1, r + 1):
    if n % i == 0:
        temp = int(i + n / i - 2)
        if count > temp:
            count = temp
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

a = int(N**0.5)
b = a+1

res = []
for i in range(1,a+1):
  if N%i == 0:
    res.append([i, int(N/i)])
    
ans = 10**12 + 10
for i in range(len(res)):
  ans = min(ans, sum(res[i]))
  
print(ans-2)

Submission status: Accepted

Solution code:
import math

# 入力
N = int(input())

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

Submission status: Accepted

Solution code:
N = int(input())

ma = int(N**0.5)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

Submission status: Accepted

Solution code:
n = int(input())


def solve(n):
    i = 1
    answer = n
    while i ** 2 <= n:
        q, r = divmod(n, i)
        if r == 0:
            answer = min(answer, i + q - 2)
        i += 1

    return answer


print(solve(n))

Submission status: Accepted

Solution code:
import math

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


if __name__ == "__main__":
    test()

Submission status: Accepted

Solution code:
n=int(input())
xlist=[]
 
for i in range(1,int(n**0.5)+1):
    if n%i==0:
        xlist.append(i)
 
ans=max(xlist)
print(int(ans+n/ans-2))

Submission status: Accepted

Solution code:

import sys
import heapq
import math

INF = float("inf")


def main():
    N = int(input())
    ans = N

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

    divisors.sort()
    return divisors


n = int(input())

result = n

tmp = make_divisors(n)

for i in range(-(-len(tmp) // 2)):

   num0 = tmp[i]
   num1 = n // num0

   result = min(result, num0 + num1 - 2)

print(str(result))