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:
import sys
from collections import Counter
from collections import deque
import math
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

def f(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())
l=f(n)
ans=10**13
for i in l:
    ans=min(ans,i+n//i-2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

d = divisor(n)

mn = 10 ** 12
for i in d:
    if (n / i) % 1 == 0:
        mn = min(n//i + i, mn)

print(mn-2 if mn != n else mn-1)

Submission status: Accepted

Solution code:
N=int(input())

from math import sqrt
M=int(sqrt(N))

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

Submission status: Accepted

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

    print(ans)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from math import ceil

def 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 res

n = int(input())
divs = divisors(n)
ans = 10 ** 12
divs.sort()
for i in range(ceil(len(divs) / 2)):
    a = divs[i]
    b = divs[(i + 1) * (-1)]
    ans = min(ans, (a - 1) + (b - 1))

print(ans)

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
from fractions import Fraction
import itertools

input=sys.stdin.readline
n=int(input())
m=math.ceil(pow(n,0.5))
for i in range(m):
    if n%(m-i)==0:
        p=m-i
        break
q=n//p
ans=q-1+p-1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


# nの約数を列挙列挙する
def make_divisors(n):
    divisors = []
    for i in range(1, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort()
    return divisors


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

    div = make_divisors(n)

    res = f_inf
    for i in div:
        cost = i + n // i - 2
        res = min(res, cost)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
t=[]
for i in range(1,int(n**0.5)+1):
  if n%i==0:
    t.append(i)
hantei=10**12+1
for i in t:
  if hantei>((i-1)+n//i-1):
    hantei=((i-1)+(n//i)-1)
print(hantei)

Submission status: Accepted

Solution code:
N = int(input())
sqrtN = N**(1/2)

minval = N

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

print(minval)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

from math import sqrt

def divisor_enumeration(n):
    div = []
    for i in range(1, int(sqrt(n))+1):
        if n % i == 0:
            if n // i != i:
                div.append((i, n // i))
            else:
                div.append((i, i))
        
    return div


def main():
    N = int(readline())

    d = divisor_enumeration(N)
    
    ans = 10**15
    for x, y in d:
        ans = min(ans, x + y - 2)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    f = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            f.append(i)
            if i * i != n:
                f.append(n // i)
        i += 1
    if n != 1:
        f.append(n)
    f.sort()
    answer = float("inf")
    for ff in f:
        answer = min(answer, ff + n // ff - 2)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

import math

n = int(math.sqrt(N)) + 1

mi = 10000000000000
for i in range(1, n+1):
    if N % i == 0:
        s = i + (N // i) - 2
        if mi > s:
            mi = s
    
print(mi)

Submission status: Accepted

Solution code:

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

N = int(input())
a = int(N ** .5)

for num in range(a):
    num = a - num
    if N % num == 0:
        b = N // num
        # print(b, num)
        print(b + num -2)
        sys.exit()

Submission status: Accepted

Solution code:
n = int(input())
tmp = 1
 
for i in range(1,10**10):
  if n%i == 0:
    if i <= n//i:
      tmp  = i
    else:
      break
  elif i >= n/i:
    break
      
print(tmp + (n//tmp) -2)

Submission status: Accepted

Solution code:
n = int(input())
tmp = 1
 
for i in range(1,10**6+1):
  if n%i == 0:
    if i <= n//i:
      tmp  = i
    else:
      break
  elif i >= n/i:
    break
      
print(tmp + (n//tmp) -2)

Submission status: Accepted

Solution code:
n = int(input())
tmp = 1
 
for i in range(1,10**6+1): #10**12とかにしてしまうとTLE　
  #たとえばn=2*大きい素数である時を考えると，この時は全回ししてまう
  if n%i == 0:
    if i <= n//i:
      tmp  = i
    else:
      break
  elif tmp == 1 and i >= n/i:
    break
      
print(tmp + (n//tmp) -2)

Submission status: Accepted

Solution code:
n = int(input())
tmp = 1
 
for i in range(1,10**6+1):
  if n%i == 0:
    if i <= n//i:
      tmp  = i
    else:
      break
  elif tmp == 1 and i >= n/i:
    break
      
print(tmp + (n//tmp) -2)

Submission status: Accepted

Solution code:
n = int(input())
tmp = 1
 
for i in range(1,10**6+1):
  if n%i == 0 and i<= n//i:
    tmp = i
   
      
print(tmp + (n//tmp) -2)

Submission status: Accepted

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

n = ni()
nn = n
mn = 10**12
nums = [1]

i=2
while i<=math.ceil(math.sqrt(n)+1):
  if n%i==0:
    nums.append(i)
  i+=1

for num in nums:
  other = nn//num
  mn = min(mn, num+other-2)

print(mn)

Submission status: Accepted

Solution code:
# C - Walk on Multiplication Table
# https://atcoder.jp/contests/abc144/tasks/abc144_c

n = int(input())

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

print(ans - 2)

Submission status: Accepted

Solution code:
n = int(input())

min = 1
max = n

while True:
    if (max - min == 1):
        sqrt = min
        break
    ave = (min + max) // 2
    if (ave**2 > n):
        max = ave
    else:
        min = ave

# print(sqrt)

for i in reversed(range(sqrt+1)):
    if (n % i == 0):
        ans = (n // i) + i -2
        break

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

print(min(can))

Submission status: Accepted

Solution code:
import math
n = int(input())
ans = n-1

for i in range(2,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())
s=int(math.sqrt(n))
m=n-1
for a in range(1,s//1+1):
    if n%a==0:
        i=a
        j=n//a
        if i+j-2<m:
            m=i+j-2
print(m)

Submission status: Accepted

Solution code:
import math
N = int(input())
lim = N
half_lim = int(math.sqrt(N)//1)
lis = [1  for i in range(0,half_lim+1,)]

result = N
for i in range(2,len(lis)):
    if lis[i] == 1:
        if N % i ==0:
            tmp = i-1  + (N//i -1)
            if result > tmp:
                result = tmp
    else :
        continue

if result ==N:
    print(result-1)
else :
    print(result)

Submission status: Accepted

Solution code:
N=int(input())

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

Submission status: Accepted

Solution code:
N = int(input())
for i in range(int(N**0.5),0,-1):
    if N%i == 0:
        break
print(N//i+i-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()
    return divisors

mi = 10**15
for i in make_divisors(n):
    a = i;b = n//i
    mi = min(mi,a+b-2)

print(mi)

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

# 約数の全列挙
def divisors(n):
    divisors = []
    R = int(n**(0.5)) + 1
    for i in range(1, R):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    # divisors.sort(reverse=True)  # ソート
    return divisors

ans = 10**18
for d in divisors(N):
    k = N // d

    ans = min(ans, d + k - 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)

    divisors.sort()
    return divisors

10
N = int(input())
divisors = make_divisors(N)
ans = float('inf')
div_len = len(divisors)
if div_len % 2 == 0:
    i = div_len // 2
    j = div_len // 2 - 1
    ans = divisors[i] + divisors[j] - 2
else:
    ans = divisors[div_len // 2] * 2 - 2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
i = 1
a,b = 1,n
while i*i <= n:
    if n % i == 0:
        a = i
        b = n//i
    i += 1


print(a+b-2)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())

    for i in range(1,n+1):
        if i*i>n:
            break
        if n%i==0:
            m=i
            l=n//i

    print(m-1+l-1)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def divisor(n):
    i = 1
    T = []
    while i * i <= n:
        if n % i == 0:
            T.append([i, n // i])
        i += 1
    return list(T)

n = int(input())
T = divisor(n)
ans = 10**20
for t in T:
    dist = (t[0] - 1) + (t[1] - 1)
    ans = min(ans, dist)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
limit = int(n**0.5)
ans = ""
for i in range(1,limit+1):
  if n%i != 0: continue
  x,y = i, n//i
  if ans == "": ans = x-1+y-1
  elif ans > x-1+y-1: ans = x-1+y-1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
ans = 10**13
for k in range(1,math.floor(math.sqrt(N))+1):
    if N % k == 0:
        ans = min(ans,k+N//k-2)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

dsts = []
for x in range(1, N + 1):
    if x ** 2 > N: break
    #
    if N % x == 0:
        dsts.append((x, N // x))

MY_INF = 10 ** 18
ans = MY_INF
for dst_x, dst_y in dsts:
    ans_tmp = abs(dst_x - 1) + abs(dst_y - 1)
    ans = min(ans, ans_tmp)

print(ans)

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(i)

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

Submission status: Accepted

Solution code:
def get_half_dividers(n):
    return {i for i in range(1, int(n ** 0.5) + 1) if n % i == 0}


N = int(input())

dividers = get_half_dividers(N)
print(min([max(0, d - 1) + max(0, (N // d) - 1) for d in dividers]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math

def f(n):
    divisor = [1]
    limit = math.ceil(math.sqrt(n))
    for n2 in range(2, limit+1):
        if n % n2 == 0:
            divisor.append(n2)
    n1 = max(divisor)
    n2 = n // n1
    print(n1 + n2 - 2)

n = int(input())
f(n)

Submission status: Accepted

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

m = 0
for i in range(2, math.ceil(math.sqrt(n)+1)):
  if n % i == 0:
    m = i

if m == 0:
  print(n-1)
else:
  print(n // m + m - 2)

Submission status: Accepted

Solution code:
import math
N = int(input())
r = math.floor(N**0.5)
l = []
for i in range(1, r+1):
    if N % i == 0:
        l.append(i + (N/i) -2)
print(int(min(l)))

Submission status: Accepted

Solution code:
n=int(input())
#a,b,x=map(int,input().split())
#hl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

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

Submission status: Accepted

Solution code:
# C - Walk on Multiplication Table
# https://atcoder.jp/contests/abc144/tasks/abc144_c

import math

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

Submission status: Accepted

Solution code:
def integerornot(n):
    if isinstance(n,int):
        return True
    if isinstance(n,float):
        return n.is_integer()
    return False

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

Submission status: Accepted

Solution code:
def primelist(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def factorization(n):
    plist = primelist(int(n**0.5))
    factor = []
    for p in plist:
        k = 0
        while n%p==0:
            k+=1
            n//=p
        if k>0:
            factor.append((p,k))
        if n==1:
            break
    if n!=1:
        factor.append((n,1))

    return factor

def 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 = divisors(n)
t = len(divs)
if t==2:
  print(divs[-1]-1)
elif t%2==0:
  print(divs[t//2-1]+divs[t//2]-2)
else:
  print(divs[t//2]*2-2)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())

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

length_list = []

for i in range(len(ND_list)):
    ND_i = ND_list[i]
    x, y  = ND_i[0], ND_i[1]
    length = x**2 + y**2
    length_list.append(length)

idx = length_list.index(min(length_list))
print(ND_list[idx][0] + ND_list[idx][1] -2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input().rstrip())
l = []
flag = True
for i in range(1,int(N**0.5)+1):
    if N % i == 0:
        l.append(i)
num = len(l)
if num==1:
    print(N-1)
else:
    ans=N-1
    for a in l:
        b=N/a
        ans = min([ans, a+b-2])
    print(int(ans))

Submission status: Accepted

Solution code:
import sys

n, *lst = map(int, sys.stdin.read().split())
sqr = int(n ** 0.5) + 1
for i in range(sqr, 0, -1):
  if not n % i:
    print(i + n // i - 2)
    quit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

i = int(N ** (1/2))
ans = 10 **13

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


print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

n = int(input())

i = round(sqrt(n))
while i > 0:
  if n % i == 0:
    print(i + n // i - 2)
    break
  i -= 1

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
import math as m


def resolve():
    N = int(input())
    minT = 10**12
    for i in range(1, int(m.sqrt(N)) + 1):
        if N % i == 0:
            j = N // i
            minT = min(minT, i + j - 2)
    print(minT)


resolve()

Submission status: Accepted

Solution code:
import math

N = int(input())

def factortwo(N):
    factors = []
    for i in range(1, int(math.sqrt(N))+1):
        if N % i == 0:
            factors.append((i, N // i))
    return factors

print(sum(factortwo(N)[-1]) - 2)

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-1+n//i-1)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
import math
import numpy as np
a=math.ceil(n**0.5)
for ii in np.arange(a,0,-1):
  b=n//ii
  if b*ii==n:
    print(ii-1+b-1)
    exit()

Submission status: Accepted

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

min = N

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

print(min)

Submission status: Accepted

Solution code:
N = int(input())

n = int(N ** 0.5)
for i in range(n, 0, -1):
  if N % i == 0:
    x = i
    y = N // x
    break

print((x-1) + (y-1))

Submission status: Accepted

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

end = int(math.sqrt(10**12))
result = 10**13
for i in range(1,end+1):
    j = n//i
    if i * j == n:
        result = min(result,i+j-2)
print(result)

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(int(i + n / i - 2))
    break

Submission status: Accepted

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

Submission status: Accepted

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

count = 1
min_move=10**12

while count <= math.sqrt(N):
    if N % count == 0:
        min_move = min(min_move, (N//count)+count -2)
    count+=1

print(min_move)

Submission status: Accepted

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

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

if minlen == 10**9:
    print(N-1)
else:
    print(minlen)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n=int(input())
flag=0
def sosuu(m):
    h=int(math.sqrt(m))
    lis=[1]
    for i in range(2,h+1):
        if m%i==0:
            lis.append(i)
    return lis
x=max(sosuu(n))
y=n//x
ans=x+y-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)
    divisors.sort()
    return divisors
N=int(input())
mem=make_divisors(N)
if len(mem)%2==0: ans=(mem[(len(mem)//2)-1]+mem[(len(mem)//2)])-2
else: ans=(mem[(len(mem)//2)]*2)-2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

n = int(input())

count = 1
ans = 10**12
while(count <= (n)**0.5):
    if n % count == 0:
        ans_tmp = (count-1) + (n//count-1)
    ans = min(ans, ans_tmp)
    count += 1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

i=int(N**0.5)
while N%i>0:
    i-=1

j=N//i
print(i+j-2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

N = int(input())

D = make_divisors(N)

ans = 10**12+1
for d in D:
    b = N//d
    if d + b < ans:
        ans = d + b
print(ans-2)

Submission status: Accepted

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

num = int(math.sqrt(n))
div = []
for i in range(1, num+1):
  if n % i == 0:
    div.append([i, n//i])
  
ans = float('inf')
for i in div:
  temp = (i[0]-1) + (i[1]-1)
  if temp < ans:
    ans = temp
print(temp)

Submission status: Accepted

Solution code:
import math

N=int(input())

N2=int(math.sqrt(N))
mins=N-1

for i in range(1,N2+1):
    if N%i==0:
        mins=min(mins,(N//i-1)+(i-1))

print(mins)

Submission status: Accepted

Solution code:
n=int(input())

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

a=make_divisors(n)
print(a[0]+a[1]-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)
    return divisors

l=make_divisors(n)

ans1=[]
ans2=[]

for value in l:
    ans1.append(value)
    ans2.append(n//value)


ans=10**13
for i in range(len(ans1)):
    ans=min(ans1[i]+ans2[i],ans)

print(ans-2)

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:
        print(i + n // i - 2)
        break

Submission status: Accepted

Solution code:
n= int(input())
import math
INF = 10**12
ans =INF
for i in range(math.floor(n**0.5)):
  if n%(i+1)==0:
    if ans > (i+1)+(n/(i+1)):
      ans = (i+1)+(n/(i+1))
print(int(ans-2))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    min = 10 ** 15
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0 and min > i + n // i - 2:
            min = i + n // i - 2
    print(min)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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


# input
N = int(input())

# div = divisors(N)
div = get_div(N)
mov = []
append = mov.append
for x in div:
    y = N // x
    append(sum([x - 1, y - 1]))

print(min(mov))

# check
cnt = 0

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
def factorization(num):
    result = []
    count = 0
    temp = num
    for i in range(2, int(num ** 0.5) + 1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp /= i
            result.append([i, count])
    if temp != 1:
        result.append([temp, 1])
    if result == []:
        result.append([num, 1])
    return result
factors = factorization(n)
exps = [range(factor[1] + 1) for factor in factors]
ans = 1001001001001
for exp0 in product(*exps):
    f0 = 1
    for i in range(len(exp0)):
        f0 *= factors[i][0] ** exp0[i]
    f1 = n // f0
    ans = min(ans, f0 + f1 - 2)
print(int(ans))

Submission status: Accepted

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

n_div = make_divisors(n)
list_ = []

for i in range(len(n_div)):
  list_.append(int(n_div[i] + (n / n_div[i])))

print(min(list_)- 2)

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools
n = int(input())

maximum = math.ceil(math.sqrt(n))
minimum = 10**20
for i in range(1,maximum+1):
    j = 0
    if n % i == 0:
        j = n / i
        minimum = min(minimum,i+j)

print(int(minimum-2))

Submission status: Accepted

Solution code:
import math

n = int(input())
ans = n
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:
n=int(input())
import math
for i in reversed(range(math.ceil(n**0.5)+1)):
  if n%i==0:
    print(n//i+i-2)
    break

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import math
    n=I()
    mini=1e+13
    for i in range(1,int(math.sqrt(n))+1):
        if n%i==0:
            mini=min(mini,i+(n//i)-2)
    print(mini)
    

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

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

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:
        print(i + N//i - 2)
        break

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    l=[]
    for i in range(1,int((n**0.5))+1):
        if n%i==0:
            a,b=i,n//i
            if a<=b:
                l.append(a+b-2)
            else:
                break
    print(min(l))
resolve()

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
from collections import Counter
def resolve():
    N,=pin()
    ans=N+1
    for i in range(1,10**6+1):
        if N%i==0:
            j=N//i
            #print(i,j)
            if j>0:
                ans=min(ans,i+j)
    print(ans-2)
    #print(B)
#%%submit!
resolve()

Submission status: Accepted

Solution code:
from math import sqrt
N = int(input())
ans = 10 ** 12
for i in range(int(sqrt(N))):
  if N % (i + 1) != 0: continue
  else: ans = min(ans, i + N // (i + 1) - 1)
print(ans)

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)
divisors.sort()
if len(divisors) % 2 == 1:
    print(2 * divisors[len(divisors) // 2] -2)
else:
    print(divisors[len(divisors) // 2] + divisors[len(divisors) // 2 - 1] - 2)

Submission status: Accepted

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


if __name__ == "__main__":
    main()