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:
n=int(input())


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

L=make_divisors(n)

s=float('inf')
for i in L:
      s=min(s,i+(n//i))

print(s-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
ans = n-1
d = 1
while d*d <= n:
    if n%d == 0:
        e = n//d
        ans = min(ans,d-1+e-1)
    d+=1
print(ans)

Submission status: Accepted

Solution code:
# i*j > (i-1)(j+1) から　i-j ができるだけ小さくなるようなi,jを選べば良い
# for i in range(1,n**0.5+1):　でn % i == 0 なら更新んすうr
n = int(input())
max_i = 0
for i in range(1,int(n**0.5)+1):
    if n % i == 0:
        max_i = i
    #print(max_i,i)
print(max_i+n//max_i-2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
d=[i for i in range(1,int(N**.5)+1)if N%i==0]
print(d[-1]+N//d[-1]-2)

Submission status: Accepted

Solution code:
def g(N):
 d=[]
 for i in range(1,int(N**0.5)+1):
  if N%i==0:
   d.append(i)
   d.append(N//i)
 return sorted(d)
d=g(int(input()))
n,m=d[len(d)//2-1:len(d)//2+1]
print(n+m-2)

Submission status: Accepted

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

divisors = get_divisors(int(input()))
n1,n2 = divisors[len(divisors)//2-1:len(divisors)//2+1]
print(n1+n2-2)

Submission status: Accepted

Solution code:
from math import sqrt, ceil
n = int(input())

ub = int(ceil(sqrt(n)))

factors = []
for i in range(1,ub+1):
        if n % i == 0:
                factors.append(i)
                if n//i != i:
                        factors.append(n//i)
      
ans = 10**18
factors.sort()
for x in factors:
        y = n // x
        ans = min(ans, y-1+x-1)
  


print(ans)

Submission status: Accepted

Solution code:
n = int(input())
import math
sqrt_n = math.floor(math.sqrt(n))

seisu_tuple = []
for a in range(1,sqrt_n+1):
    if n/a == math.floor(n/a):  # 整数判定
        seisu_tuple.append((a,n/a))
bunkai_list_sum = [sum(x) for x in seisu_tuple]
min_tuple = seisu_tuple[bunkai_list_sum.index(min(bunkai_list_sum))]
print(int(sum(min_tuple) - 2))

Submission status: Accepted

Solution code:
import sys

# import numpy as np
import math
from fractions import gcd
from collections import deque
import bisect

sys.setrecursionlimit(1000000)


def main():
    # map(int, input().split())
    # l = list(map(int, input().split()))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())

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

Submission status: Accepted

Solution code:
# coding : utf-8

N = int(input())
end = int(N ** 0.5)

for j in range(end, 0, -1):
    if N % j == 0:
        i = N//j
        answer = i+j-2
        break
print(answer)

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline
#str 注意
def main():
    n = int(input())
    root = int(math.sqrt(n))
    ans = 10**100
    for i in range(1,root+1):
        if n%i==0:
            ans = min(ans,i+n//i)
        else:
            pass
    print(ans-2)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N = int(input())
factor = []
tmp = int(math.sqrt(N))
while N%tmp!=0:
  tmp -= 1
print(int(tmp+(N/tmp)-2))

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import math
 
N = int(input())
sqrtN = int(math.sqrt(N))
x = 0
 
for i in range(1,sqrtN+1)[::-1]:
    if N % i == 0:
        x = i
        break
 
y = N // x
print(x+y-2)

Submission status: Accepted

Solution code:
import math
N = int(input())
a = 1
b = N
nn = math.sqrt(N)
n = math.ceil(nn)

for i in range(2, n+1):
    if N % i == 0:
        j = N // i    
        if (i + j) < (a + b):
            a = i
            b = j

print(a + b -2)

Submission status: Accepted

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

Submission status: Accepted

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

N = int(input())
ans = solve(N)
print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())

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

Submission status: Accepted

Solution code:
import math
N = int(input())
root = math.ceil(math.sqrt(N))
for i in range(root):
  if N % (root-i) == 0:
    sho = N/(root-i)
    print(int(sho+root-i-2))
    break

Submission status: Accepted

Solution code:
import math

N = int(input())

step = N - 1

for i in range(2, N):
    if N % i == 0:
        if step > (i - 1) + ((N / i) - 1):
            step = (i - 1) + ((N / i) - 1)

    if i > math.sqrt(N):
        break
print(int(step))

Submission status: Accepted

Solution code:
import math

N=int(input().strip())

ans=N+2
for i in range(1,math.floor(N**0.5)+1):
    if N%i==0:
        a=i
        b=N//a
        if a+b<ans:
            ans=a+b

print(ans-2)

Submission status: Accepted

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

for x in range(1, int(n ** 0.5)+1):
  if n % x == 0:
    y = n/x
    li.append(x+y-2)  
     
result = min(li) 
print(int(result))

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq

MOD = 10**9+7

N = int(input())
r = math.ceil(math.sqrt(N))

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

import math

min_m=10**20

for i in range(1,N):

    if i*i > N:
        break

    if N%i==0:
        j=N/i

        if i+j < min_m:
            min_m=i+j

print(int(min_m-2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N=int(input())
import math
ij=[N,N]
n=math.floor(math.sqrt(N))

for itemp in range(n):
    i=itemp+1
    if N%i==0:
        if sum(ij)>i+N/i:
            ij=[i,N/i]
print(int(sum(ij)-2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N = int(input())
ans = N

for x in range(1, int(math.sqrt(N)) + 1):
    if N % x == 0:
        if ans > x + int(N / x) - 2:
            ans = x + int(N / x) - 2
print(ans)

Submission status: Accepted

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

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

def main():
    Min = 2000000000000
    divisors = make_divisors(int(input()))
    if len(divisors)%2==1:
        divisors.append(divisors[len(divisors)-1])
    #print(divisors)
    for i in range(0,len(divisors)-1,2):
        Min = min(divisors[i]+divisors[i+1],Min)
    print(Min-2)

main()

Submission status: Accepted

Solution code:
n = int(input())
r = int(n**0.5)
revList = [i for i in range(r+1)]
revList = revList[1:]
revList.reverse()

for i in revList:
  if n % i == 0:
    res = int(n/i) + i - 2
    break
print(res)

Submission status: Accepted

Solution code:
import math

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

res = 10 ** 12

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

print(res)

Submission status: Accepted

Solution code:
if __name__ == '__main__':

	n = int(input())
	m = int(n//2)

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

	print(end)

Submission status: Accepted

Solution code:
n = int(input())
ans = 10**20
a = n ** 0.5
a = int(a)
for i in range(a+1):
  if i ==0:
    continue
  if n % i != 0:
    continue
  j = n/i
  j = int(j)
  ans = i+j-2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = 10**20
a = n ** 0.5
a = int(a)
for i in range(a+1):
  if i ==0:
    continue
  if n % i != 0:
    continue
  j = n/i
  j = int(j)
  ans = min(ans, i+j-2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = n
for i in range(1, 1000001):
    if n % i == 0:
        if ans > (i-1) + (n//i -1):
            ans = (i-1) + (n//i -1)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
import sys
import math
list=[]
for i in range(0,int(math.sqrt(n))):
    if n%(i+1)==0:
        list.append(i-1+(n/(i+1)))

print(int(min(list)))

Submission status: Accepted

Solution code:
n=int(input())

d=[]
for h in range(1, int(n**0.5)+1):
	if n%h == 0:
		j=n//h
		d.append(j)
		i=n//j

print(i-1+j-1)

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
qN=int(np.sqrt(N))
d = [i +  N//i - 2 if N%i==0 else 10**13 for i in range(1,qN+1)]
print(min(d))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
limit_of_a = int(pow(N, 1/2))+1

result = 1000000000001

for a in range(1, limit_of_a):
    if N % a == 0:
        b = N // a
        result = min(result, a+b-2)

print(result)

Submission status: Accepted

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


def main():
    N = int(input())
    rslt = divisor(N)
    print(rslt[-1][0] + rslt[-1][1] - 2)
    return


main()

Submission status: Accepted

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


def main():
    N = int(input())
    print(divisor(N)[-1][0] + divisor(N)[-1][1] - 2)
    return


main()

Submission status: Accepted

Solution code:
n = int(input())

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

ans = i-1 + j-1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=10**18
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())
n = round(N**0.5)
a = 0
b = 0
for i in range(n):
    if N%(n-i)==0:
        a = n-i
        b = int(N/a)
        break
print(a+b-2)

Submission status: Accepted

Solution code:
n = int(input())
ans = 10000000000000000;
i = 1
while(i * i <= n):
  if(n % i == 0):
    ans = min(ans , n // i + i-2)
  i += 1
print(ans)

Submission status: Accepted

Solution code:
# 2019-11-19 19:43:48(JST)
import sys
# import collections
import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n = int(sys.stdin.readline().rstrip())

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N = int(input())

route_N = math.sqrt(N)

# a+b-2 minimum
# a*b = N 

ans = 10e+12

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

print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())

Ans = 10**12

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

Submission status: Accepted

Solution code:
import math
a = int(input())
b = math.floor(a**0.5)
for i in range(b):
  if a % (b-i) == 0:
    c = b-i
    d = a //(b-i)
    break
print(c+d-2)

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:
        a = i
        b = n/i
        if a+b < ans:
            ans = a+b

print(int(ans-2))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())

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

R = divisor(n)
S = []
for i in range(len(R)):
  S.append(R[i] + n//R[i] - 2)
  
print(min(S))

Submission status: Accepted

Solution code:
N = int(input())
ans = N - 1
a = 2
while a*a <= N:
    b = N // a
    if a * b == N:
        ans = min(ans, a + b - 2)
    a += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
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
  
x = make_divisors(n)
div = sorted(x)[len(x)//2]
print(n // div + div - 2)

Submission status: Accepted

Solution code:
import math
n = int(input())
ans = 10e+12
for a in range(1, int(math.sqrt(n))+1):
    if n % a == 0:
        b = n // a
        x = a + b - 2
        ans = min(x, ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n = int(input())
g = 10 ** 15
a = math.floor(math.sqrt(n))
for i in range(1, a + 1):
    b = math.floor(n / i)
    if i * b == n:
        f = i + b - 2
        if g >= f:
            g = f
print(g)

Submission status: Accepted

Solution code:
import math 

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
if n==divisors[-1]**2:
    print(divisors[-1]*2-2)
else:
    print(divisors[-1]+divisors[-2]-2)

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())
divs = make_divisors(N)
if len(divs) % 2 == 0:
    print(divs[len(divs)//2 - 1] + divs[len(divs)//2] - 2)
else:
    print(divs[len(divs)//2] * 2 - 2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N=int(input())
k=math.sqrt(N)
t_c=int(k)
t_c=t_c+1
t_r=0
for i in range(t_c):
  if N % (t_c-i)==0:
    t_r=N//(t_c-i)
    t_c=t_c-i
    break
print(t_c-1+t_r-1)

Submission status: Accepted

Solution code:
import math
int_n = int(input())
i = (math.sqrt(int_n))
i = math.floor(i)
while i >= 1:
    if int_n % i == 0:
        j = int_n/i
        print(math.floor((i - 1) + (j - 1)))
        break
    i = i - 1

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

half = int(N**(1/2) + 1)

a=1
b=10**12
for i in range(1,half+1):
    if N%i == 0:
        if abs(a-b) > abs(i - N/i):
            a = i
            b = N//i

print(abs(a-1+b-1))

Submission status: Accepted

Solution code:
import math
n, = map(int, raw_input().split())
n_s = int(math.sqrt(n))
ans = float('inf')
for i in range(1, n_s+1):
    if n % i == 0:
        j = n//i
        ans = min(ans, (i-1+j-1))

print ans

Submission status: Accepted

Solution code:
N=int(input())
a=int(N**0.5)+1#約数の最大限
answer = float('inf')
for i in range(1,a):
  if N%i==0:
    answer = min(answer,i+(N//i-2))
print(answer)

Submission status: Accepted

Solution code:
from math import sqrt, ceil


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

    pairs = [(i, n // i) for i in range(1, ceil(sqrt(n)) + 1) if n % i == 0]

    least_distance = min(map(lambda x: x[0] + x[1], pairs))

    print(least_distance - 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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)

    return divisors

ret = int(input())
r=make_divisors(ret)
if(len(r)%2==1):
    print(r[-1]*2-2)
else:
    for i in range(0,int(len(r)/2)):
        if(r[i*2]+r[i*2+1]-2<ret):
            ret=r[i*2]+r[i*2+1]-2
    print(ret)

Submission status: Accepted

Solution code:
import numpy as np
 
N = int(input())
ans = 10**12
for i in range(int(np.sqrt(N)+0.5)):
  a = i+1
  if N % a != 0:
    continue
  step = a + int(N/a) -2
  if step < ans:
    ans = step
print(ans)

Submission status: Accepted

Solution code:
import math


class Solution:
    def solve(self, n: int) -> int:

        maxDivisor = int(math.sqrt(n) + 0.5)

        for i in range(1, maxDivisor + 1):
            if n % i == 0:
                p = i

        q = n // p

        return p+q-2


if __name__ == '__main__':

    # standard input
    n = int(input())

    # solve
    solution = Solution()
    print(solution.solve(n))

Submission status: Accepted

Solution code:
n = int(input())

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

distance = 10 ** 12

i = 1

while i * i <= n:
  if n % i == 0:
    m = int(n / i)
    move = (m - 1) + (i - 1)
    if move < distance:
      distance = move
  i += 1

print(distance)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n=int(input())

base = int(math.ceil(math.sqrt(n)))

while True:
	
	if  n % base == 0:
		a = base
		break
		
	else:
		base -= 1
		
b = n // a

print(a+b-2)

Submission status: Accepted

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

s = math.floor(math.sqrt(n))
#print(math.floor(math.sqrt(n)))

while n%s != 0:
  s -= 1
s2 = n // s
#print(s,s2)
print(s+s2-2)

Submission status: Accepted

Solution code:
import random
def p(n):
    r = []
    a, b = 0, 2
    while b * b <= n:
        if n % b == 0:
            n //= b
            r += [b]
        else:
            b += 1 + a
            a = 1
    if n > 1 : r += [n]
    return r
n = int(input())
m = p(n)
ans = n-1
for i in range(2048):
    random.shuffle(m)
    a = 1
    b = n
    for i in m:
        if a >= b : break
        b //= i
        a *= i
    ans = min(ans, a+b-2)
    
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# coding: utf-8

# 整数 > 整数型
def I(): return int(input())

# 整数列 '1 2 3 4' > 整数型リスト
def IsIl(): return list(map(lambda x: int(x), input().split()))

# 改行挟む整数列　'1/n 2/n 3/n' > 整数型りすと
def InIl(n): return [input() for i in range(n)]

# 整数列 '1 2' > 整数型タプル
def IsIt(): return map(lambda x: int(x), input().split())

# 改行挟む整数列　'1\n 2\n 3\n' > 整数型たぷる
def InIl(n): return map(input() for i in range(n))

# 文字列 'abcd' > 文字型リスト
def SsSl(): return list(map(lambda x: x, input()))

# 整数 '1234' > 整数型リスト

# 文字列 'aba' > 辞書（文字型:個数）{'a':2,'b':1}
def SSd():
    from collections import defaultdict
    A = input() # [int(i) for i in input().split()]
    dd=defaultdict(int)
    for a in A:
        dd[a]+=1
    return dd

import math

n=I()

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

Submission status: Accepted

Solution code:
import math

N = int(input())

def trial_division(target):
  dest = int(math.sqrt(target))

  for i in range(dest, 1, -1):
    if target % i == 0:
      return i
  
  return 1

A = trial_division(N)
B = int(N / A)
print(A + B - 2)

Submission status: Accepted

Solution code:
N = int(input())

min_i = 1
min_j = N

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n = int(input())
r_n = math.ceil(math.sqrt(n))

for i in range(r_n, 0, -1):
    if not n % i:
        ans = [i, n/i]
        break

print(int(sum(ans)-2))

Submission status: Accepted

Solution code:
N = int(input())
lim = int(N ** 0.5) + 1
cand = [N-1]
for i in range(2, lim):
    if N % i == 0:
        j = N // i
        cand.append(i - 1 + j -1)
print(min(cand))

Submission status: Accepted

Solution code:
n = int(input())
ans = float('inf')
 
for i in range(1, 10**6+1):
    q, m = divmod(n, i)
    if m == 0:
        ans = min(ans, q+i)
 
print(ans-2)

Submission status: Accepted

Solution code:
n = int(input())

def make_divisors(n):
    ans =10**12
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            a = i
            b = n//i
            if a+b-2 < ans:
                ans = a+b-2
            
    # divisors.sort()
    return ans

ans = make_divisors(n)

print(ans)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
s = int(input())
dir = 1000000000000000000000
for i in range(1,int(s**0.5//1)+1):
	if s%i == 0:
		a = i
		b = s/i
		if a+b-2 < dir:
			dir = int(a + b - 2)
if s == 2:
  dir = 1
print(dir)

Submission status: Accepted

Solution code:
# ABC144c


def main():
    import sys
    import math
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    # map(int,input().split())
    n = int(input())
    ans = 10**12
    for i in range(math.ceil(math.sqrt(n))+1, 0, -1):
        if n % i == 0:
            ans = min(ans, i+n//i)
    print(ans-2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math 

n = int(input())
a=0
b=0
root_n  = math.sqrt(n)
#繰り上げ
root_n = math.ceil(root_n)
yakusuu =[]
for i in range(1,root_n+1):
    if(n%i == 0):
        yakusuu.append(i)
a = max(yakusuu)
b = n / a
print(int(a+b-2))

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())

i=1
ans=n

while i * i <= n:
    j,m = divmod(n,i)
    if m == 0:
        ans = min(ans, i+j-2)
    i += 1

print(ans)

Submission status: Accepted

Solution code:
from numpy import sqrt

n=int(input())

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

Submission status: Accepted

Solution code:
from math import sqrt,floor

def main():
    n = int(input())
    rn = floor(sqrt(n))
    movestep = 10**12
    for i in range(1, rn + 1):
        if n % i == 0:
            step = i + int(n / i) - 2
            if movestep > step:
                movestep = step
    print(movestep)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import sqrt,floor

def main():
    n = int(input())
    rn = floor(sqrt(n))
    movesteps = set()
    for i in range(1, rn + 1):
        if n % i == 0:
            movesteps.add(i + int(n / i) - 2)
    print(min(movesteps))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n= int(input())
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

res  = []
if is_prime(n):
    res.append(n - 1)
else:
    for t in range(1, int(math.sqrt(n)) + 1):
        if n % t == 0:
                res.append(n//t + t - 2)


print(min(res))

Submission status: Accepted

Solution code:
import math

n= int(input())
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

i, j = 10**12, 10**12
res  = 0
if is_prime(n):
    res = n - 1
else:
    for t in range(1, int(math.sqrt(n)) + 1):
        if n % t == 0:
            a, b = t, n//t
            if a + b < i + j:
                i, j = a, b
    res = i + j -2


print(res)

Submission status: Accepted

Solution code:
import math

N = int(input())
n = math.sqrt(N)
ans = 10 ** 12

for i in range(1 , math.ceil(n) + 1):
  if i * (N // i) == N:
    count = (i - 1) + ((N // i) - 1)
    ans = min(ans , count)
    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S = []
for k in range(1,N):
    if k**2 <= N:
        if N % k == 0:
            S.append(N/k+k-2)
        else:
            continue
    if k**2 > N:
        break
print(int(min(S)))

Submission status: Accepted

Solution code:
import math

N = int(input())

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

Submission status: Accepted

Solution code:
import math
n = int(input())
ans = 9999999999999
for i in range(1, math.ceil(math.sqrt(n+1))):
    x1 = i
    x2 = n // x1
    if x1 * x2 == n and x1 + x2 < ans:
        ans = x1-1 + x2 -1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dc_max = 1
temp = int(N**0.5)
for i in range(1,int(N**0.5)+1):
  if N%i == 0:
    dc_max = i

print((dc_max -1)+(N//dc_max-1))

Submission status: Accepted

Solution code:
N = int(input())

Nlist = []

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

Submission status: Accepted

Solution code:
n = int(input())
ans = float('inf')

for i in range(1, 10**6+1):
    q, m = divmod(n, i)
    if m == 0:
        ans = min(ans, q+i)

print(ans-2)

Submission status: Accepted

Solution code:
import math

N = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())


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


r = make_divisors(n)

i = len(r)//2
j = i-1

if len(r) % 2 == 1:
    print(r[i]-1+r[i]-1)
    exit()

print(r[i]-1+r[j]-1)