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())
sq=int(n**0.5)
a=1; b=n
for i in range(1,sq+1):
    if n%i==0:
        a=i
        b=n//i
print(a+b-2)

Submission status: Accepted

Solution code:
def pf(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

num = int(input())
ls = pf(num)
if len(ls) % 2 == 0:
  print(ls[len(ls)//2-1]+ls[len(ls)//2]-2)
else:
	print(ls[len(ls)//2]*2 -2)

Submission status: Accepted

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

import sys

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
#        for line in sys.stdin:
#            lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    n = [int(e) for e in lines[0].split(" ")][0]

    return (n,)


def solve(n,):


    a = 0
    b = 0
    c = int(pow(n, 0.5))
    if debug:
        log("c=%s" % c)
    for i in range(c, 0, -1):   

        if n % i == 0:
            a = i
            b = n // i
            if debug:
                log("a=%s" % a)
                log("b=%s" % b)
            break


    return  a - 1 + b - 1


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, end=' ')
    else:
        print("%s" % result)

if __name__ == '__main__':

    main()

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

ans = make_divisors(N)
ans.sort()


while len(ans)>2:
    ans = ans[1:-1]
if len(ans)==1:
    n = ans[0]
    print((n-1)*2)
else:
    a = ans[0]
    b = ans[1]
    print(a+b-2)

Submission status: Accepted

Solution code:
n=int(input())

i=1
best = -1
while i*i <= n:
    if n%i == 0:
        val = i+(n//i)
        if best == -1 or val < best:
            best = val
    i += 1

print(best-2)

Submission status: Accepted

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

_n = int(input())


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


chker(_n)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = False

# debug = True
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

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    N = II()
    divisors = []

    sq = N**0.5
    nearest = -1

    for i in range(1, int(N**0.5)+1):
        if N % i == 0:
            divisors.append(i)
            if abs(sq - nearest) > abs(sq-i):
                nearest = i
    dprint(nearest, N//nearest)
    print((nearest-1)+(N//nearest)-1)
solve()

Submission status: Accepted

Solution code:
import math
N =int( input())
M = math.floor(math.sqrt(N)) + 1

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

Submission status: Accepted

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

# nの約数列挙
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass  # sortされていない

dv = divisor(N)
dv.sort()
num = len(dv)
pos1 = dv[int(num/2) - 1]
pos2 = dv[int(num/2)]
dist = pos1 + pos2 - 2
print(dist)

Submission status: Accepted

Solution code:
N = int(input())

def max_div(n):
    maximum = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            maximum = i
    return maximum

P = max_div(N)
Q = N // P

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


    # divisors.sort()
    return divisors
  
i = input()
A = int(i.split(' ')[0])

print(min(make_divisors(A))-2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 27 21:13:33 2019

@author: doppe
"""

import math

N = int(input())

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

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

    # divisors.sort()
    return divisors

n = int(input())
l = make_divisors(n)
a = 0
b = 0
min = 10**13
for i in range(len(l)):
    a = l[i]
    b = n/l[i]
    if (a-1) + (b-1) < min:
        min = (a-1) + (b-1)
print(int(min))

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)
        break

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
import bisect
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    n = II()
    a = 1

    for  i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            a = i

    print(a + n//a - 2)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math

def solve(n):
    start = int(math.sqrt(n))
    # print("start", start)
    for i in range(start+1, 0, -1):
        # print(i)
        if (n / i).is_integer(): 
            print(i - 1 + (n // i) - 1)
            return
    print("wrong...")

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    solve(n)

Submission status: Accepted

Solution code:
from math import sqrt
n = int(input())
ij = []
i = 0
nr = int(sqrt(n))+1
while (i<=nr):
    i += 1
    r = n % i
    if (r != 0):
        continue
    j = n // i
    ij.append(i+j-2)
#print(ij)
print(min(ij))

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

a = make_divisors(N)

ans = []

for i in a:
    j = N//i
    ans.append(i-1+j-1)

print(min(ans))

Submission status: Accepted

Solution code:
a=int(input())

r=int(a**(1/2))

k=r
while a%k != 0:
  k -=1
  
ans= k + a//k -2



print(ans)

Submission status: Accepted

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

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def calc(x):
    ret = (1, x)
    for i in range(1, 10**6+1):
        if i*i > x:
            break
        if x % i == 0:
            if i + x //i < ret[0]+ret[1]:
                ret = (i, x//i)
    return ret

def main():
    n = ri()
    ret = calc(n)
    print(ret[0]+ret[1]-2)


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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


def main():
    n = int(input())
    d = make_divisors(n)
    p = [d[i:i+2] for i in range(0, len(d), 2)]

    if len(d) % 2 != 0:
        tmp = p[-1]
        p[-1] = tmp + tmp

    arr = []
    for x, y in p:
        arr.append(x+y)

    print(min(arr)-2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

minimum=n-1
for i in range(1,n2+1):
    if(n%i==0):
        minimum=min(minimum,(n//i-1)+(i-1))

print(minimum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys

a=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
    
divisors = make_divisors(a)
b = max([i for i in divisors if i <= a**(1/2)])
print(int(a/b + b - 2))

Submission status: Accepted

Solution code:
N = int(input())

i_guess = int(N**0.5)
j_found = 0
i_found = 0
while i_found == 0:
    if N%i_guess == 0:
        i_found = i_guess
        j_found = int(N/i_found)
    else:
        i_guess -= 1

print(i_found+j_found-2)

Submission status: Accepted

Solution code:
import math
def f(n):
    mx=0
    for i in range(2,1+int(math.sqrt(n))):
        if n%i==0:
            mx=i
    if mx==0:
        mx=1
    return mx

def main():
    N=int(input())
    fact1=f(N)
    return fact1+N//fact1-2

print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# = map(int, input().split())
n = int(input())
# = input()
# = list(map(int, input().split()))

nlst = []
for i in range(1, int(n**(1/2))+1):
	if n%i == 0:
		nlst.append(i)

x = nlst[len(nlst)-1]
print(x + n//x - 2)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
min = n - 1
for i in range(2,int(np.sqrt(n))+1):
    if n%i == 0:
        distance = (i-1)+(int(n/i)-1)
        if min > distance:
            min = distance
print(min)

Submission status: Accepted

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


 
k=int(math.sqrt(n)//1)
#print(k)

for i in range(k):
  if n%(k-i)==0:
    print(int(k-i-1+n//(k-i)-1))
    exit()

Submission status: Accepted

Solution code:
import math

N=int(input())

p = int(N**0.5)

while p > 0:
    if N%p == 0:
        tup = (p, N//p)
        break
    p -= 1
#print(tup)
print(tup[0] + tup[1] - 2)

Submission status: Accepted

Solution code:
N = int(input())
from math import sqrt
res = set()
for i in range(int(sqrt(N)+1),0,-1):
  if N%i==0:
    res |= {N//i+i-2}
print(min(res))

Submission status: Accepted

Solution code:
import math
n = int(input())
sq_n = round(math.sqrt(n))
m = 0.0

for i in range(1, sq_n + 1):
    m = n/i
    #print(m)
    if (m.is_integer()):
        maxm = m
        maxi = i

print(int(maxm+maxi-2))

Submission status: Accepted

Solution code:
N = int(input())

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

ans = float('inf')
for xy in divs:
    ans = min(ans, xy[0] + xy[1] - 2)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = b = 1

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

print(a+b-2)

Submission status: Accepted

Solution code:
def sim_fact(inp):
  n = 1
  pairs = []
  while n * n <= inp:
    if inp % n == 0:
      pairs.append([n, inp//n])
    n += 1
  return pairs

pairs = sim_fact(int(input()))
print(min([sum(pair) for pair in pairs]) - 2)

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())

def divset(n:int) -> list:
    l = []
    if n <= 0:
        return l
    
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            l.append((i, n // i))
    return l


l = divset(N)
ans = l[0]
n = ans[0] + ans[1]
for e in l[1:]:
    if e[0] + e[1] < n:
        ans = e
        n = e[0] + e[1]

print(n - 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

tem = make_divisors(n)

ln = len(tem)


if ln%2==0:
    result = (tem[int(ln/2-1)]-1)+(tem[int(ln/2)]-1)
else:
    result = (tem[int(ln//2)]-1)*2

print(result)

Submission status: Accepted

Solution code:
# N = m x n (m <= n) と表される時、m <= √n である
# この時の最大となるmを求める
import math

N = int(input())

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

Submission status: Accepted

Solution code:
import math

N = int(input())

n = math.floor(math.sqrt(N))

for p in range(n, 0, -1): # p = n, n-1, ..., 1
    if N % p == 0:
        q = N // p
        break

print((q - 1) + (p - 1))

Submission status: Accepted

Solution code:
N = int(input())

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

print(i+N//i-2)

Submission status: Accepted

Solution code:
N = int(input())

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

ms = []
for m in range(1,rN+1):
	if N % m != 0:
		continue
	
	ms.append((m-1)+((N // m)-1))
	#print((m-1),((N // m)-1))
	
print(min(ms))

Submission status: Accepted

Solution code:
import math
import sys
N = int(input())
sqN = N ** (1/2)
sqN = math.floor(sqN)


for i in range(sqN,0,-1):
  if N % i == 0 :
    print(int(i-1 + (N/i) - 1))
    sys.exit()

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

divisors = make_divisors(N)

a = 1
b = N
sum_ab = 1+N
for n in (divisors):
    tmp_a = n
    tmp_b = N//n
    tmp_ab = tmp_a + tmp_b
    if tmp_ab < sum_ab:
        sum_ab = tmp_ab
        a = tmp_a
        b = tmp_b

ans = a+b-2
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

N = int(input())
n = round(math.sqrt(N))+2

minmin = 10**20
for i in range(1,n):
    com = N/i
    if N % i == 0:
        c = com + i - 2
        if minmin >= c:
            minmin = c

print(int(c))

Submission status: Accepted

Solution code:
import sys
import math
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
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
div_l = make_divisors(n)
if len(div_l) % 2 == 0:
    m1 = div_l[len(div_l) // 2]
    m2 = div_l[len(div_l) // 2-1]
    print(m1+m2-2)
else:
    m = div_l[len(div_l) // 2]
    print(m*2 - 2)

Submission status: Accepted

Solution code:
import math

n = int(input())

near_sqrt_n = math.floor(math.sqrt(n))

for i in range(near_sqrt_n,0,-1):
    if (n%i==0):
        target=(i, int(n/i))
        break

print(target[0]+target[1]-2)

Submission status: Accepted

Solution code:
n=int(input())

ans=1001001001001001
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())
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

arr = sorted(make_divisors(N))

if len(arr)%2==0:
  i=arr[len(arr)//2-1]
  j=arr[len(arr)//2]
else:
  i = arr[len(arr)//2]
  j = arr[len(arr)//2]
print(i+j-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  
sosu = make_divisors(n)

leng = len(sosu) 
if leng %2 ==1:
  print(sosu[(leng-1)//2]*2-2)
else:
  print(sosu[leng//2]+sosu[(leng//2)-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
X=make_divisors(N)
m=N
for i in range(len(X)//2):
    if X[2*i]+X[2*i+1]-2 < m:
        m=X[2*i]+X[2*i+1]-2
if len(X)%2==1:
    if 2*X[-1]-2<m:
        m=2*X[-1]-2
print(m)

Submission status: Accepted

Solution code:
import numpy as np

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


def main():
	#A, B = [int(x) for x in input().split()]
	N = int(input())
	
	R = make_divisors(N)
	A = 10**12
	B = 10**12
	M = 10**12
	for a, b in R:
		if M > max(a, b):
			M = max(a, b)
		A = a
		B = b
	print(A - 1 + B - 1)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
a = int(input())
half = int(a ** .5)
for num in range(half, 0, -1):
  if a / num == int(a/num):
    if num == 1 or a/num == 1:
      print(max(a//num, num) - 1)
      break
    else:
      print(a//num + num - 2)
      break

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    min_step = 10**12
    for i in range(1, int(N**0.5)+1):
        if N % i == 0:
            x = N / i
            if x < min_step:
                min_step = int(x) + i - 2
    print(min_step)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def prime_factorize(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())
ls = prime_factorize(n)
for i in range(len(ls)):
  ans = []
  pair = n // ls[i]
  ans.append(ls[i] + n // ls[i] - 2)
 
ans.sort()
print(ans[0])

Submission status: Accepted

Solution code:
N = int(input())


nums = []
denom = int(N ** .5)

min_value = N - 1

while (1):
  if denom < 2:
    break
  if N % denom == 0:
    min_value = min(min_value, denom + N / denom - 2)
  denom -= 1
print(int(min_value))

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)

if len(r) % 2 == 1:
    a = r[len(r)//2]
    print((a-1)+(a-1))
else:
    a = int(len(r)/2)
    print((r[a-1]-1)+(r[a]-1))

Submission status: Accepted

Solution code:
n = int(input())
def make_divisors(n):
    k = 0
    divisors = []
    for i in reversed(range(1, int(n**0.5)+1)):
        if n % i == 0:
            k = i
            break
    # divisors.sort()
    return k
k = make_divisors(n)
kk = n // k
print(kk + k - 2)

Submission status: Accepted

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

n_sqrt = int(math.sqrt(n))
ans1 = 1
ans2 = n

for i in reversed(range(n_sqrt+1)):
    if n%i==0:
        ans1 = i
        ans2 = n//i
        break
print(ans1+ans2-2)

Submission status: Accepted

Solution code:
def answerA():
    a, b = map(int, input().split())
    if a < 10 and b < 10:
        result = a * b
    else:
        result = -1

    print(result)


def answerB():
    def can_be_devided_by_1d(n):
        result = 'No'
        for i in range(1,10):
            floor, mod = divmod(n, i)
            if mod == 0 and floor < 10:
                result = 'Yes'
        return result

    n = int(input())
    print(can_be_devided_by_1d(n))


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

    n = int(input())
    divisors = make_divisors(n)
    candidates = set()

    for i in divisors:
        floor = n // i
        distance = (floor-1) + (i-1)
        candidates.add(distance)

    print(min(candidates))


if __name__ == '__main__':
    answer()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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 = set(table)
    return table

n = int(input())
ds = divisor(n)

step = n
for d in ds:
    r = n / d
    step = min(step, d+r-2)

print(int(step))

Submission status: Accepted

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


ans = 99999999999999999
for i in range(1, int(limit)+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
s = math.floor(math.sqrt(n))
for i in range(s,0,-1):
    if n%i==0:
        a = i
        break
b = n//a

print(a+b-2)

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    t = n
    mt = 10 ** 20
    for i in range(1, int(n ** 0.5) + 1):
        if t % i == 0:
            mt = min(mt, (i - 1) + (t // i - 1))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        if 2 not in a:
            a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in a:
                a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
a = prime_factorize(N)

import math

lis = []
for n in range(1, int(math.sqrt(N)) + 1):
    if N % n == 0:
        lis.append(n)
t, u = N // max(lis) - 1, max(lis) - 1

i, j = N // max(a) - 1, max(a) - 1

ans = min(t + u, i + j)
print(ans)

Submission status: Accepted

Solution code:
def c():
    n = int(input())
    div = make_divisors(n)
    mid = len(div) // 2
    i = div[mid]
    j = n // i
    print(i + j - 2)

    return


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


if __name__ == '__main__':
    c()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False
input = sys.stdin.readline
if em: sys.stdin = open('/dev/tty')
N = int(input())
import math
facts = []
for i in range(1, math.ceil(math.sqrt(N))+1):
  if N % i == 0:
    facts.append([i, N//i])
sums = []
for fact in facts:
  sums.append(sum(fact))
if em : embed()
print(min(sums)-2)

Submission status: Accepted

Solution code:
n = int(input())

ans = [1]*2
for i in range(1,n+1):
    if i * i <= n:
        if n//i * i == n:
            ans[0] = i
            ans[1] = n//i
    else:
        break
print(sum(ans)-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n = int(input())

x = int(math.sqrt(n)) + 1
while True:
    if n % x == 0:
        break
    else:
        x -= 1

res = x + n // x - 2
print(res)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


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

    sqrt_n = math.ceil(math.sqrt(n)) + 1
    ans = 10**12 + 1
    for i in range(1, sqrt_n):
        q, mod = divmod(n, i)
        if mod == 0:
            ans = min(ans, i + q - 2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())

        divisors = self.make_divisors(N)
        a, b = 1, N
        for d in divisors:
            if a + b > d + N // d:
                a = d
                b = N // d

        print(a + b - 2)

    def make_divisors(self, n: int):
        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


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

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

import math

def devident(N):
    sq = int(math.sqrt(N))
    for m in range(sq, 1, -1):
        if N % m == 0:
            return (m, N // m)
    return (N, 1)


def solve(N):
    m, n = devident(N)
    return m+n-2

if __name__ == '__main__':
    N = int(input())

    ans = solve(N)

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

Submission status: Accepted

Solution code:
N = int(input())
gcdlst = []
for i in range(1, int(N ** 0.5) + 1):
    if N % i == 0:
        gcdlst.append(i)
        if i != N // i:
            gcdlst.append(N // i)
gcdlst.sort()
tmplen = len(gcdlst)
if tmplen % 2 == 0:
    tmplen = tmplen // 2
    ans = gcdlst[tmplen] + gcdlst[tmplen - 1] - 2
else:
    tmplen = tmplen // 2
    ans = (2 * gcdlst[tmplen]) - 2
print(ans)

Submission status: Accepted

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

n=int(input())
l=[]
i=int(n**(0.5))+1
ans=0
while 1:
    if n%i==0:
        ans=n//i+i-2
        break
    i-=1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n=int(input())

root=int(n**(1/2))

yakusu=1
for i in range(1,1+root):
    if(n%i==0):
        yakusu=i
print(yakusu+(n//yakusu)-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())
if (N ** 0.5).is_integer():
    num1 = int(N ** 0.5)
    num2 = num1
else:
    arr = make_divisors(N)
    num1 = arr[len(arr)//2 - 1]
    num2 = N // num1
print(num1 + num2 - 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

div_list = make_divisors(n)

a = div_list[-1]
b = div_list[-2]
if n == a * a:
    print(a + a - 2)
else:
    print(a + b - 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:
        if (N//i) + i < ans:
            ans = (N//i) + i
print(ans - 2)