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

sys.setrecursionlimit = 10 ** 6
N = int(input())


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


def dfs(i, x):
    global N
    global res
    if i != len(prime_keys):
        p = prime_keys[i]
        for num in range(prime[p] + 1):
            x_ = x * (p ** num)
            y = N // x_
            res = min(res, x_ + y - 2)
            dfs(i + 1, x_)


prime = Counter(prime_factorize(N))
prime_keys = list(prime.keys())
res = N * 2
dfs(0, 1)
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

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

factor.sort()
print(factor[0]-2)

Submission status: Accepted

Solution code:
N=int(input())
ans=[]
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
ans=make_divisors(N)
print(ans[0]-2)

Submission status: Accepted

Solution code:
# coding: utf-8
def make_divisors(n):
    divisors = []
    ans = 10**12
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            x, y = i, n//i
            if ans > x-1 + y-1:
                ans = x - 1 + y - 1
    return ans

N = int(input())
print(make_divisors(N))

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

list = make_divisors(N)
M = len(list)
if M % 2 == 1:
    ans = (list[-1]-1)* 2
else:
    ans = (list[-1]-1) + (list[-2]-1)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

a = []
m = math.floor(n**(1/2))
for i in range(1,m + 1):
    if n % i == 0:
        a.append(i + (n/i) - 2)

print(int(min(a)))

Submission status: Accepted

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

mini = n - 1

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

print(mini)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
num = int(input())
print(min(i + num // i - 2 for i in range(1, int(num ** (1 / 2)) + 1) if not num % i))

Submission status: Accepted

Solution code:
import sys
import itertools
import bisect

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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 = ni()

li = make_divisors(n)
#print(li)
res = 10 ** 12 + 1
m = len(li)
for i in range(m//2 + 1):
    res = min(li[i] - 1 + li[-(i + 1)] - 1, res)
    # print(res, li[i] - 1 + li[-i] - 1)
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N=int(input())
c=[]
flag=0
for x in range(1, math.ceil(pow(N,1/2))+1):
    if N%x==0:
        c.append(x+N//x-2)
print(min(c))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

N=int(input())

result=1000000000000

i=1

if isPrime(N)==True:
    print(N-1)
else:
    for i in range(1,int(math.sqrt(N))+1):
        i+=1
        if(N%i==0):
            buf=i-1+N/i-1
            if(buf <= result):
                result=buf
    print(int(result))

Submission status: Accepted

Solution code:
#ABC-144-C
N = int(input())
root_N = N ** 0.5
ans = 10 ** 13

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

print(int(ans))

Submission status: Accepted

Solution code:
import math

N = int(input())

res = 10 ** 15
for i in range(1, int(math.sqrt(N))+1):
    if N%i == 0:
        res = min(res, N // i + i)

print(res-2)

Submission status: Accepted

Solution code:
import sys
from math import sqrt

[nstr] = sys.stdin.readline().split(" ")
n = int(nstr)

for i in range(int(sqrt(n)), 0, -1):
    r = float(n) / float(i)
    if not r.is_integer():
        continue
    j = int(r)
    print(i-1 + j-1)
    exit()

Submission status: Accepted

Solution code:
N = int(input())
n = int((N**(1/2))//1)
s =[0]*(n+10)
for i in range(1,n+1):
  if N%i == 0:
    s[i] = i
maxs = s[0]
for j in range(1,n+1):
  if s[j] > maxs:
    maxs = s[j]
p = int(N/maxs)
walk = p + maxs - 2
print(walk)

Submission status: Accepted

Solution code:
from math import sqrt

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

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


List = make_divisors(N)

if len(List) % 2 == 1:
    print(List[len(List) // 2] * 2 - 2)
else:
    print(List[len(List) // 2 - 1] + (List[len(List) // 2] - 2))

Submission status: Accepted

Solution code:

# a<=bとみなせるので探索回数は√nでよい
import math
n = int(input())
r_n = int(math.sqrt(n))+1
m = 10 ** 12
for i in range(1,r_n):
  if n % i == 0 and m > i + n / i - 2:
    m = i + n / i - 2
 
print(int(m))

Submission status: Accepted

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

ans = np.inf
for i in range(1, 10**6+1):
    if n%i: continue
    j = n//i
    ans = min(ans, i +j -2)

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
こるぼー = print

n = int(input())

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

こるぼー(ans)

Submission status: Accepted

Solution code:
n = int(input())

こるぼー = float("inf")
for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        j = n // i
        こるぼー = min(こるぼー, i + j - 2)

print(こるぼー)

Submission status: Accepted

Solution code:
n = int(input())
step = float('inf')
import math
k = math.floor(math.sqrt(n))+1
for i in range(1,k+1):
    div, mod = divmod(n,i)
    if mod == 0 and i + div - 2 < step:
        step = i + div -2
print(step)

Submission status: Accepted

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

def main():
    n = int(input())
    a_max = int(math.sqrt(n))
    min_v = 10 ** 12
    for a in range(1, a_max+1):
        if n % a == 0:
            min_v = min(min_v, a + (n//a) - 2)
    print(min_v)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def solve(N: int):
    ans = 100000000000000000
    amax = math.floor(math.sqrt(N))
    for i in range(1,amax+1):
        if N % i == 0:
            ans = min(ans, i+(N/i)-2)
    print(math.floor(ans))
    
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

res = float('inf')
for x in range(1, int(n**0.5) + 1):
    if n % x == 0:
        res = min(res, x-1 + n//x -1)
print(res)

Submission status: Accepted

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

a=[]
b=[]
z=[]
for i in range(1,round(math.sqrt(N))+1):
    if N%i==0:
        a.append(i)
        b.append(N//i)
    else:
        continue

for j in range(len(a)):
    z.append(a[j]+b[j]-2)

print(min(z))

Submission status: Accepted

Solution code:
N = int(input())
ans = int(10e13)
i = 1

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
s = 0
N = int(input())
for i in range(1, int(N**(1/2))+1):
    if N%i == 0 and i > s:
        s = i
print(s+(N//s)-2)

Submission status: Accepted

Solution code:
import math
n=int(input())
m=math.floor(n**0.5)
while(n%m!=0):
  m -= 1
print(m + n//m - 2)

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
N = int(input())
max_int = int(N**0.5)
for v in reversed(range(max_int+1)):
    if N % v == 0:
        w = int(N/v)
        print(v+w-2)
        break
    else:
        pass

Submission status: Accepted

Solution code:
import math
N = int(input())
ij = int(math.sqrt(N)//1)

for i in range(1,ij+1):
    if N%i == 0:
        num = i

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

Submission status: Accepted

Solution code:
from math import sqrt, ceil

N = int(input())
sq = ceil(sqrt(N))
min_st = N - 1

for i in range(2, sq + 1):
    if N % i == 0:
        if i + N // i - 2 < min_st:
            min_st = i + N // i - 2

print(min_st)

Submission status: Accepted

Solution code:
from math import sqrt

n = int(input())

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

Submission status: Accepted

Solution code:
import math

N = int(input())

# 時間削減のため、2乗して該当の数字に一番近いところから計算を始める
# その次に割り切れる数が見つかれば 2乗して近い数字 * i
for i in range(int(math.sqrt(N)), 0, -1):
    # 余りがないので割り切れる最大値
    if N % i == 0:
        ans = i+(N//i)-2
        print(ans)
        break

Submission status: Accepted

Solution code:
import math

def main():
    N = int(input())
    rt_N = math.ceil(math.sqrt(N))

    mn_ij = 10**12
    for i in range(1, rt_N+1):
        if N % i == 0:
            j = N // i

            mn_ij = min(mn_ij, i+j)
        
        mn_ij = min(mn_ij, i+j)

    # print(list(map(len,[ st, facs]) ))
    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n= int(input())
tmp = float('inf')
for i in range(1,1000001):
	if n % i == 0:
		tmp =min(tmp,i + n/i -2)

print(int(tmp))

Submission status: Accepted

Solution code:
from math import floor
from math import sqrt
n=int(input())
nn=floor(sqrt(n))
rest=n%nn
while rest!=0:
    nn-=1
    rest=n%nn
nnn=n/nn
print(int(nn+nnn-2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
Abs = int(np.sqrt(N))
if Abs ** 2 == N:
    print(Abs + Abs - 2)
else:
    min = N + 1
    min_i = 1
    for i in range(1, Abs + 1):
        tmp = N // i
        if tmp * i == N:
            if min > tmp:
                min = tmp
                min_i = i
    print(min + min_i - 2)

Submission status: Accepted

Solution code:
N = int(input())

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

print(int(min(ans)))

Submission status: Accepted

Solution code:
from math import sqrt, ceil

N = int(input())
sq = ceil(sqrt(N))
min_st = N-1

for i in range(2, sq+1):
    if ((N % i) == 0):        
        if (i + N//i - 2 < min_st):
            min_st = i + N//i-2

print(min_st)

Submission status: Accepted

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

    i = 1
    ans = 10 ** 18

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

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

X = int(np.sqrt(N))

if X * X < N:
  X = X + 1

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

Submission status: Accepted

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

print(min(r)-2)

Submission status: Accepted

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

to=int(math.sqrt(n))
a=n*2
for i in range(1,to+1):
    if n%i==0:
        a=min(a,n//i+i)

print(a-2)

Submission status: Accepted

Solution code:
N = int(input())
x = N
y = N
ansx = N
ansy = N
ans = []
n = int(N**0.5)
if N**0.5 == int(N**0.5):
    print(int(N**0.5)*2-2)
else:
    for i in range(n+1):
        if N%(i+1) == 0:
            ans.append(i+1)
    ans.append(N)
    if(ans[1]==N):
        print(N-1)
    else:
        for i in range(len(ans)):
            if ansx+ansy>ans[i] + int(N//ans[i]):
                ansx = ans[i]
                ansy =int(N//ans[i])
        print(ansx + ansy -2)

Submission status: Accepted

Solution code:


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

def out(N, table):
    r = 0
    for i in table:
        a = i
        b = N / i
        if r > (a-1)+(b-1) or r == 0:
            r = (a-1)+(b-1)
    return int(r)


N = int(input())
table = divisor(N)
r = out(N, table)
print(r)

Submission status: Accepted

Solution code:
N = int(input())
root_N = int(N**0.5)
def table():
    for i in range(root_N,0,-1):
        if N%i==0:
            return i
a = table()
b = N//a
print(a+b-2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = float(input())
import numpy as np
d = 1
for i in range(2,int(np.floor(N**0.5))+1):
	if N%i==0:
		d = i
print(int(d+N/d-2))

Submission status: Accepted

Solution code:
#ABC144-C Walk on Multiplication Table

N = int(input())
for i in reversed(range(1,int(N ** 0.5)+1)): #forの逆向きの回し方。このやり方以外だとrangeがNoneを返しやすい?
    if N % i == 0:
        print(i + N//i -2)
        break

Submission status: Accepted

Solution code:
def solve(n: int) -> int:
  for i in reversed(range(1, int(n**(1/2)) + 1)):
    if n % i == 0:
      j = n // i
      return i + j - 2
  assert(False)


n = int(input().strip())
print(solve(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math as m

N = int(input())
ans = [1, N]
for i in range(1, m.ceil(m.sqrt(N)) + 1):
    if N % i == 0 and N // i - i < (ans[1] - ans[0]):
        ans = [i, N // i]
print(sum(ans) - 2)

Submission status: Accepted

Solution code:
N=int(input())
import sys
import math
ANS = sys.maxsize
i_max = math.ceil(N ** 0.5)

for i in range(1, i_max + 1):
  if N % i != 0:
    continue
  j = N // i
  ANS = min(i+j-2, 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

dist_list = []

for dj in make_divisors(N):
    if N % dj != 0:
        continue
    di = N / dj
    dist_list.append(
        [int(dj + di - 2), [di, dj]]
    )

dist_list.sort(key=lambda x: x[0])
print(dist_list[0][0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
data = list(map(int,input().split()))
N = data[0]
i = 1
b = 0
c = float('inf')
while (N / i >= i):
  a = N / i
  b = N % i
  if b == 0:
    r1 = int(i)
    r2 = int(a)
    if (r1 + r2) < c:
      c = int(r1 + r2)
  i = i + 1
print(c-2)

Submission status: Accepted

Solution code:
N = int(input())
result = int(10e13)

for i in range(1,int(pow(N,0.5)+1)):
    if N%i!=0: continue
    else: result = min(N//i+i,result)
print(result-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    def c(x):
        return 1 <= x <= 9
    if c(a) and c(b):
        print(a * b)
        return
    print(0)
    return

#B
def B():
    a = set()
    for i in range(10):
        for K in range(10):
            a.add(i * k)
    x = II()
    if x in a:
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    n = II()
    factlize = []
    ans = inf
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            ans = min(ans, n // i + i - 2)
    print(ans)

    return

#D
def D():
    return

#E
def E():
    def solve(m):
        a1 = a[::-1]
        f1 = f[::1]
        res = 0
        for i in range(n):
            if a1[i] * f1[i] <= m:
                continue
            k = m // f1[i]
            res += a1[i] - k
            if res > K:
                return False
        return True

    n, K = LI()
    a = LI()
    a.sort()
    f = LI()
    f.sort()
    ok = max(a) * max(f)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    print(ok)
    return

#F
def F():
    return


#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n = int(input())
sq_n = int(math.sqrt(n))
s_lis = []
e_lis = []
for i in range(1, sq_n + 1):
    if n % i == 0:
        s_lis.append(i)
        e_lis.append(n // i)
min_len = n + 1 - 2
for s, e in zip(s_lis, e_lis):
    min_len = min(min_len, s + e - 2)
print(min_len)

Submission status: Accepted

Solution code:
import math


def walk_on_multiplication_table(n: int) -> int:
    minimum = None
    for i in range(1, int(math.sqrt(n)) + 1):
        tmp = int(n % i)
        if tmp == 0:
            r = i + int(n / i) - 2
            if minimum is None:
                minimum = r
            else:
                minimum = min(minimum, r)
    return minimum

if __name__ == '__main__':
    N = int(input())
    result = walk_on_multiplication_table(N)
    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:
        ans = i+(N//i)-2
        print(ans)
        break

Submission status: Accepted

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

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_list = make_divisors(N)
if len(N_list) % 2 == 1:
    odd = len(N_list) / 2 
    i = N_list[int(odd)]
    ans = (i - 1)*2
else:
    even = len(N_list) / 2
    i = N_list[int(even) - 1]
    j = N_list[int(even)]
    ans = i+j-2

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n=int(input())

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

print(ans)

Submission status: Accepted

Solution code:
import math
import sys

n = int(input())

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

Submission status: Accepted

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

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:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict
def primefactor(n):
     ans=defaultdict(int)
     for i in range(2,int(n**0.5+1)):
         while n%i==0:
             ans[i] += 1
             n //= i
     if n>1:
         ans[n]=1
     return dict(ans)

from itertools import product
from functools import reduce

def main():
    N=int(input())
    d=primefactor(N)

    ans = N - 1
    for v in product(*[range(i+1) for i in d.values()]):
        a = reduce(lambda x, y: x*y, [x**y for x, y in zip(d.keys(), v)])
        b = N // a
        ans = min(a-1 + b-1, ans)

    print(ans)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc144","c",main)

Submission status: Accepted

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict
def primefactor(n):
     ans=defaultdict(int)
     for i in range(2,int(n**0.5+1)):
         while n%i==0:
             ans[i] += 1
             n //= i
     if n>1:
         ans[n]=1
     return dict(ans)

from itertools import product
from functools import reduce

def main():
    N=int(input())
    d=primefactor(N)
    f=list(d.keys())
    v=[list(range(i+1)) for i in d.values()]
    ans = N - 1
    for i in product(*v):
        a = reduce(lambda x, y: x*y, [x**y for x, y in zip(f, i)])
        b = N // a
        ans = min(a-1 + b-1, ans)

    print(ans)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc144","c",main)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

div = 1
ans = 10 ** 12

while n >= div ** 2:
    if n % div == 0:
        ans = n // div + div - 2
    div += 1

print(ans)

Submission status: Accepted

Solution code:
import math
def get(n):
    a=math.sqrt(n)
    #print(a,'a')
    i,j=int(a),int(a)
    if a%1==0:
        return 2*a-2
    z=True
    while i>=1 and z:
        if n%i==0:
            z=False
        else:
            i-=1
    #print(i,'i')
    z=True
    k=n//i
    return int(k-1+i-1)
n=int(input())
print(int(get(n)))

Submission status: Accepted

Solution code:
import math

N = int(input())

n = math.floor(math.sqrt(N)) + 1
lens = [N-1]
for a in range(2, n):
  if N % a == 0:
    lens.append(a+N//a-2)

print(min(lens))

Submission status: Accepted

Solution code:
import math

N = int(input())

n = int(math.sqrt(N)) + 1
lens = [N-1]
for a in range(2, n):
  if N % a == 0:
    lens.append(a+N//a-2)

print(min(lens))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
array = []
for i in range(1,10**6+1):
    if N%i == 0:
      array.append(i + (N//i))
amin = min(array)
print(amin - 2)

Submission status: Accepted

Solution code:
N = int(input())

def find_divisors(N):
    divisors = []
    for A in range(1, int(N**0.5) + 1):
        if N % A == 0:
            divisors.append(A)
#            B = N//A
#            if A != B:
#                divisors.append(B)
    divisors.sort()
    return divisors

divisors_of_N = find_divisors(N)

# total number of steps to reach a point (A,B) is equal to (A-1)+(B-1) = A+B-2
num_steps = N+1
for A in divisors_of_N:
    B = N//A
    num_steps = min(num_steps, A+B)

print(num_steps - 2)

Submission status: Accepted

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

N = int(input())

sum_min = 10**12+1
ab = None

for a in range(1, int(math.sqrt(N))+1):
    if N % a == 0:
        b = N//a
        if b >= a and a+b-2 < sum_min:
            sum_min = a+b-2
            ab = (a, b)

print(sum_min)

Submission status: Accepted

Solution code:

import math

N = int(input())

res = 10**12+1

if N==1:
    print(0)
else:
    for a in range(1, int(math.sqrt(N))+1):
        if (N%a)==0:
            b = int(N/a)
            if res>a+b-2:
                res = a+b-2
    
    if res == 10**12+1:
        print(N-1)
    else:
        print(res)

Submission status: Accepted

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

import numpy as np

N = int(readline())

U = 10**6 + 100

div = np.arange(1, U, dtype=np.int64)
div = div[N%div==0]

div = np.union1d(div, N//div)

answer = (div + (N//div)).min() - 2
print(answer)

Submission status: Accepted

Solution code:
import math
n = int(input())
l = [0]

for i in range(1, int(math.sqrt(n))+1):
  if n % i == 0:
    l[0] = i

print(l[0]+(n//l[0])-2)

Submission status: Accepted

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

for i  in range(1, int(N**(1/2))+1):
    if N % i == 0:
        List_ans.append(i)
        
x = max(List_ans)
y = N//x

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

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:
import numpy as np
N = int(input())
result = []
for i in range(1, np.sqrt(N).astype(int)+1):
    if N % i == 0:
        result.append(i+int(N/i)-2)
print(min(result))

Submission status: Accepted

Solution code:
def factorization(n):
  primen = []
  degree = []
  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
      primen.append(i)
      degree.append(cnt)
  if temp!=1:
    primen.append(temp)
    degree.append(1)
  if primen==[]:
    primen.append(n)
    degree.append(1)
  return primen,degree

N = int(input())
ans = factorization(N)
import itertools
T = []
for i in ans[1]:
  T.append(list(range(i+1)))
L = list(itertools.product(*T))
RR = N
for i in L:
  x = 1
  for j in range(len(ans[0])):
    x = x * (ans[0][j]**i[j])
  y = N // x
  R = x - 1 + y - 1
  RR = min(RR,R)
print(RR)

Submission status: Accepted

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

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

Submission status: Accepted

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

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)

times = 10**12

for j in range(len(divisors)):
    x = divisors[j]
    y = n // x
    time = (x -1) + (y - 1)
    if time < times:
      times = time
print(times)

Submission status: Accepted

Solution code:
N = int(input())
sqn = int(N**0.5//1)
#print(sqn)
for n in range(sqn):
    sqt = sqn-n
    div = N/sqt
    if div%1 == 0:
        ans = sqt+N/sqt-2
        intans = int(ans)
        print(intans)
        exit()
    else:
        pass

Submission status: Accepted

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