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:
def get_divisors(n):
    res = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n//i)
    return sorted(res)
    
N = int(input())
ds = get_divisors(N)

res = 10**12

if len(ds) % 2 != 0:
    # 平方数の場合
    for i in range((len(ds)+1) // 2):
        res = min(res, ds[i] + ds[-(i+1)])
else:
    # 平方数でない場合
    for i in range(len(ds) // 2):
        res = min(res , ds[i] + ds[-(i+1)])
        
print(res - 2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

Submission status: Accepted

Solution code:
import math

n=int(input())
start=int(math.sqrt(n)//1)
#print(start)
List=[]
for i in range(1,start+1):
  if (n%i==0):
    List.append(i)
    List.append(int(n//i))
num=len(List)
#print(List)
print(List[num-2]+List[num-1]-2)

Submission status: Accepted

Solution code:
#--------------------------------------------
#ライブラリ等
import sys
import math
from math import sqrt
input = sys.stdin.readline

#---------------------------------------------
N = int(input())
for i in range(int(sqrt(N))+1,-1,-1):
    if N % i == 0:
        print(int(i+(N/i)-2))
        exit()

Submission status: Accepted

Solution code:
import array
import sys
from collections import deque
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
#S = deque(list(input()))

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

Submission status: Accepted

Solution code:
n = int(input())
ans = 10 ** 12
for i in range(1, int(n**.5) + 2):
  if n % i == 0:
    step = i + n // i - 2
    ans = min(ans, step)
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)

    # divisors.sort()
    return divisors
n=int(input())
d=make_divisors(n)
if d[-1]**2==n:
    print(2*d[-1]-2)
else:
    print(d[-1]+d[-2]-2)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = -1
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            a = i
            b = n // i
            if ans == -1:
                ans = a + b - 2
            else:
                ans = min(ans,a + b - 2)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#C - Walk on Multiplication Table
N = int(input())
for i in range(int(N**0.5),1,-1):
    if N % i == 0:
        A = N//i
        print(A+i-2)
        exit()
    else:
        pass
print(N-1)

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(reverse=True)
    return divisors

l = make_divisors(n)
ans = float('inf')
for i in l:
    ans = min(ans, i-1+n//i-1)
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
a = math.floor(N ** 0.5)

ans = N
for x in range(1, a + 1):
  if N % x != 0: continue
  y = N // x
  if ans > x + y - 2:
    ans = x + y - 2
print(ans)

Submission status: Accepted

Solution code:
import math


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())
divisors = make_divisors(n)

ans = 10**13
for i in range(math.ceil(len(divisors)/2)):
    #print(divisors[i], divisors[len(divisors)-i-1])
    #print(divisors[i]+divisors[len(divisors)-i-1])
    ans = min(ans, divisors[i]+divisors[len(divisors)-i-1]-2)
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:
        continue
    j = n//i
    ans = min(ans, i + j - 2)
print(ans)

Submission status: Accepted

Solution code:
a = int(input())
c = [j for j in range(1,int(a**0.5)+1) if a%j==0]
if c:
    print((max(c)-1) + (a//max(c)-1))
else:
    print(a-1)

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

ans = pow(10, 30)
for i in range(1, int(pow(n, 0.5)) + 1):
    if n / i == n // i:
        j = n // i
        if i + j - 2 < ans:
            ans = i + j - 2
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from math import sqrt
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

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

if __name__ == '__main__':
    main()

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:continue
    j=n//i
    t=i+j-2
    ans=min(t,ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
num=int(n**0.5)
ans=float('inf')
for i in range(1,num+1):
    if n%i==0:
        temp=n//i+i-2
        if ans>temp:ans=temp

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
ans = inf
for i in reversed(range(1, int(sqrt(n)) + 1)):
    if n % i == 0:
        ans = min(ans, i + n // i - 2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

masu_min = min(make_divisors(n))

print(masu_min - 2)

Submission status: Accepted

Solution code:
import math
a = int(input())
num = math.ceil(a**(1/2)+1)
for i in range(1,num+1):
  num1,num2 = divmod(a,i)
  if num2 == 0:
    ans1 = num1
    ans2 = i
print(ans1+ans2-2)

Submission status: Accepted

Solution code:
N=int(input())

ans=N+1
maxi=N
j=1

while maxi/j>1:
    maxi=N//j
    if N%j==0 and j+N//j<ans:
        ans=j+N//j
    j=j+1

print(ans-2)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

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

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

Submission status: Accepted

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

a = 1
while a <= math.sqrt(N):
  if N % a == 0:
    b = N // a
    len = (a + b) - 2

    if (ans == 0) or (ans > len):
      ans = len
  a += 1

print(ans)

#まだ途中エラーが出ているので明日取り組む

Submission status: Accepted

Solution code:
n = int(input())
cnt_min = float('inf')
for i in range(1,int(n**0.5)+1):
    if n%i==0:
        cnt = i + n//i -2
        if cnt < cnt_min:
            cnt_min = cnt
print(cnt_min)

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 + n//i)
    return divisors
#
print(min(make_divisors(n))-2)

Submission status: Accepted

Solution code:
N = int(input())
count_min = float('inf')
for i in range(1, int(N**0.5)+1):
    if N % i == 0:
        count = i + N // i - 2
        if count < count_min:
            count_min = count

print(count_min)

Submission status: Accepted

Solution code:
import math
n=int(input())
lst=[]
down=math.floor(math.sqrt(n))
for i in range(1,down+1):
    #if i**2>n:
    #    break
    if n%i==0:
        lst.append(i+n//i)
print(min(lst)-2)

Submission status: Accepted

Solution code:
import math
n=int(input())
lst=[]
down=math.floor(math.sqrt(n))
for i in range(1,down+1):
    #if i**2>n:
    #    break
    if n%i==0:
        lst.append(i+n//i)
print(min(lst)-2)

Submission status: Accepted

Solution code:
import math
n=int(input())
lst=[]
down=math.floor(math.sqrt(n))
for i in range(1,down+1):
    if i**2>n:
        break
    if n%i==0:
        lst.append(i+n//i)
print(min(lst)-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
lst=[]
for i in range(1,n):
    if i**2>n:
        break
    if n%i==0:
        lst.append(i+n//i)
print(min(lst)-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())
X = make_divisors(N)
if len(X) % 2:
    i = X[int((len(X)-1)/2)]
    j = X[int((len(X)-1)/2)]
else:
    i = X[int((len(X))/2)]
    j = X[int((len(X))/2-1)]    

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

Submission status: Accepted

Solution code:
N = int(input())

ans = N**2
for i in range(1, int(N**(1/2))+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())
maximum_x = int(n ** (0.5))

move = 0


def gen():
    for x in range(1, maximum_x + 1):
        if n % x == 0:
            yield x + int(n/x) - 2


print(min(gen()))

Submission status: Accepted

Solution code:
import math

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

while n % a != 0:
    a -= 1

b = n // a
print(a + b - 2)

Submission status: Accepted

Solution code:
import math

N = int(input())

a = int(math.sqrt(N))

while N % a != 0:
    a -= 1

b = N // a
print(a + b -2)

Submission status: Accepted

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

Submission status: Accepted

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

print(min(l) - 2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def prime(n):
    for k in range(2,int(math.sqrt(n)+1)):
        if n!=k and n%k==0:
            return False
    return True
#素数判定

ans=0
if prime(n)==True:
    ans=n-1
else:
    for k in range(r):
        if n%(r-k)==0:
            ans=(r-k)+(n//(r-k))-2
            break

print(ans)

Submission status: Accepted

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

m = float('inf')
pair = [0,0]
for i in range(1,int(math.sqrt(N))+1):
    if N % i == 0:
        if int(N/i) - i < m:
            m = int(N/i) - i
            pair = [int(N/i),i]

t = pair[0] + pair[1] - 2
print(t)

Submission status: Accepted

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

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

print(A[-1] + n//A[-1] - 2)

Submission status: Accepted

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

N = int(input())

sq = int(math.sqrt(N))

for i in range(sq, 0, -1):
    if N % i == 0:
        a = i
        b = N // i
        break

print(a+b-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
mini = float('inf')
n_iter = int(n**(1/2)+2)

for i in range(1, n_iter):
    if n%i==0:
        a, b = i, int(n/i)
        dist = (a-1) + (b-1)
        mini = min(mini, dist)

print(mini)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
t=int(n**0.5)+2
ans=10**18

for i in range(1,t):
    if n%i==0:
        if ans>(i-1)+((n//i)-1):
            ans=(i-1)+((n//i)-1)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
s = np.sqrt(n)
for i in range(int(s)):
    if n % (int(s)-i) == 0:
        print(int(s)-i-1 + n//(int(s)-i)-1)
        break

Submission status: Accepted

Solution code:
N = int(input())
ans = 10 ** 12
i = 0
while i * i <= N:
    i += 1
    if N % i != 0:
        continue
    j = int(N / i)
    cand = i + j - 2
    ans = min([cand, ans])
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
lis=make_divisors(n)
x=lis[-1]
if n%x**2==0:
    print(x*2-2)
    exit()
print(lis[-1]+lis[-2]-2)

Submission status: Accepted

Solution code:
import sys
argVec = sys.argv
if len(argVec) > 1:
    GBN_DEBUG = True
else:
    GBN_DEBUG = False

#S = input()
N = int(input())
#S, T = input().split()
#N, M = map(int, input().split())
#W = [input() for _ in range(N)]
#A = A = list(map(int, input().split()))

def dprn(s, i):
    if GBN_DEBUG:
        print(", " + s + " = " + str(i), end = "")

def dprns(s):
    if GBN_DEBUG:
        print(", " + s, end = "")

def dprni(i):
    if GBN_DEBUG:
        print(str(i), end=" ")

def puts(s):
    print(s)

def puti(i):
    print(str(i))

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

div = 1
for i in range(sqrtN, 0, -1):
    if (N % i) == 0:
        div = i
        break

#ans = N / div + div - 2
ans = N // div + div - 2
puti(ans)

Submission status: Accepted

Solution code:
N = int(input())


def divisors(n):
    ret = set()
    for i in range(1, int(n**(0.5))+1):
        if n % i == 0:
            ret.add(i)

    return(ret)


ans = N-1
for x in divisors(N):
    ans = min(ans, x-1+(N//x)-1)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#B
N=int(input())
fac=[]
for i in range(1,10**6+1000):
  if N%i==0:
    fac.append((i,N//i))
ans=10**19
for l,r in fac:
  ans=min(l-1+r-1,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    Ans = 1000000000000000000000
    for i in range(1, N + 1):
        if i ** 2 > N: break
        if N % i == 0:
            di, dj = i, N // i
            Ans = min(Ans, di + dj - 2)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def divisor(n): #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


N = INT()
# print(divisor(N))
ans = INF
for d in divisor(N):
    r = N // d
    ans = min(ans, r+d-2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

a = math.floor(N ** 0.5) + 1
ans = N + 1
for i in range(1, a):
  j = N // i
  if i * j == N and i + j - 2 < ans:
    ans = i + j - 2
  
print(ans)

Submission status: Accepted

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

if r > 0:
    print(r+(N//r)-2)
else:
    print(N-1)

Submission status: Accepted

Solution code:
N = int(input())

a, b = 1, N
for n in range(2,N):
    if n*n == N:
        a = b = n
        break
    elif n*n > N:
        break
    elif N%n == 0:
        a, b = n, N//n

print(a+b-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())
divisors = make_divisors(n)

ans = 10**12
if len(divisors) % 2 == 0:
    for i in range(0, len(divisors), 2):
        ans = min(ans, divisors[i]+divisors[i+1])

else:
    for i in range(0, len(divisors)-1, 2):
        ans = min(ans, divisors[i]+divisors[i+1])
    ans = min(ans, divisors[-1]*2)
print(ans-2)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc144/tasks/abc144_c

n=int(input())

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

div=divisors(n)

ans=float('inf')
for e in div:
    ans=min(ans,(e+n//e)-2)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

tmp = pow(10, 13)
for i in range(1, int(pow(n, 0.5)) + 1):
    if n % i == 0 and abs(n // i - i) < tmp:
        tmp = abs(n // i - i)
        ans1 = n // i
        ans2 = i
#print(tmp, ans1, ans2)
print(ans1 + ans2 - 2)

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(reverse=True)
    return divisors

l = make_divisors(n)
ans = float('inf')
for a in l:
    b  = n//a
    ans = min(ans, a+b-2)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

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

print(temp)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

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

n = INT()
a = make_divisors(n)
print(a + n // a - 2)

Submission status: Accepted

Solution code:
def main():
    from math import sqrt
    N = int(input())
    ans = 10**12
    for i in range(1, int(sqrt(N))+3):
        if N % i:
            continue
        j = N//i
        ans = min(ans, i+j-2)
    print(ans)


if __name__ == '__main__':
    main()

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:
n = int(input())
n2 = int(n ** 0.5)
ans = n

for i in range(1,n2 + 1):
  if n % i == 0:
    ans1 = i + n/i - 2
    ans = min(ans,ans1)
    
print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
res = 10 ** 15
for i in range(1, int(n ** .5) + 1):
    if n % i == 0:
        j = n // i
        res = min(res, i + j - 2)
print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
import math

def main():
    N = int(input())
    ubound = int(math.sqrt(N))
    minv = 10**12 + 100
    for i in range(1, ubound+1):
        if N % i == 0:
            ab = i + (N//i) - 2
            minv = min(minv, ab)
    print(minv)

if __name__ == '__main__':
    main()

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
     
N = int(input())
     
m = N - 1#mはNが素数だった時の保険
for i in range(1, math.floor(N ** 0.5) + 1):
#当該整数の2分の1乗まで考えれば距離計算の最小値は導出できるためこうしている
#math.floor(x)はxの小数点以下の切り捨てを行っている．
        if N % i == 0:
            m = min(m, math.floor(i + (N / i) - 2))
     
print(m)

# N = int(input())
     
# m = N - 1
# for i in range(1, N):#これだと計算オーダーが大きくなりすぎてTLEになる
#         if N % i == 0:
#             m = min(m, math.floor(i + (N / i) - 2))
#             #iが割るやつ
# print(m)

Submission status: Accepted

Solution code:
import math

N = int(input())

m = N - 1
for i in range(1, math.floor(N ** 0.5) + 1):
    if N % i == 0:
        m = min(m, math.floor(i + (N / i) - 2))

print(m)

Submission status: Accepted

Solution code:
n = int(input())
ans = 10**12
for i in range(1, int(n**0.5)+1):
  if n%i == 0:
    l = (i+(n/i)-2) #-2は(0,0)->(1,1)の分
    ans = min(ans, l)
print(int(ans))

'''
10^12 以下の 正整数 N が与えられます。
この整数を i×j (i,j∈N) と表したとき，i+j−2 の最小値を求める問題です。
まず，愚直に考えると [1, N] の範囲で 2 重ループを回し，ij=N となる 2 整数の和の最小値を更新すればよいです。しかし，これは O(N2) となり，到底間に合いません。
ここで，約数 (つまり，ij=N, i≤j となる i,j すべて) を列挙する際，一方の約数 i は N−−√ 以下であることを利用します。もう一方の約数 j は N÷i から求まるので，すべての約数は O(N−−√) で求まることがわかります。
あとは，すべての i,j の組を列挙し，i+j−2 の最小値を求めれば良いです。1×N=N であることは自明なので，1+N–2=N–1 を初期値にしておきましょう。

計算量 O(N−−√)
'''

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


n = load()

ps = []
for i in range(1, int(math.sqrt(n))+1):
    if n % i ==0:
        ps.append((i, int(n/i)))
if not ps:
    print(n-1)
    exit()
mn = min(ps, key=lambda p: p[0] + p[1])
print(mn[0]-1 + mn[1]-1)

Submission status: Accepted

Solution code:
def func(N):
    loop = int(N ** 0.5)

    ans = float("inf")
    for i in range(1, loop + 1):
        if N % i:
            continue
        j = N // i
        tmp = i + j - 2
        ans = min(ans, tmp)
    
    return ans


if __name__ == "__main__":
    N = int(input())
    
    print(func(N))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    loop = int(N ** 0.5)

    ans = float("inf")
    for i in range(1, loop + 1):
        if N % i == 0:
            j = N // i
            tmp = i + j - 2

            if tmp < ans:
                ans = tmp
    print(ans)


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:
        b = N // i
        ans = min(ans, i + b - 2)
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
r = math.floor(math.sqrt(N))
#print(r)
for i in range(r):
    if N%(r-i)==0:
        l=N/(r-i)
        r=r-i
        break
#print(l,r)
print("{:}".format(int(r+l-2)))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
from collections import deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

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

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

    print(minroute)




resolve()

Submission status: Accepted

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