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

a = []

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


a.sort()

print(a[0] - 2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()

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

    print(sum(fact[-1]) - 2)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [input() for _ in range(n)]

def divisors(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            if (i*i != n):
                table.append(n//i)
        i+=1
    return table

n = int(input())

tbl = divisors(n)
ans = []

for i in tbl:
    tmp = i + n//i -2
    ans.append(tmp)

print(min(ans))

Submission status: Accepted

Solution code:
N = int(input())


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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
i = 1
ans = 0
while i**2<=N:
    if N%i==0:
        ans = (i+(N//i)-2)
    i += 1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def factors(n):
    d = []
    a = 2
    while n >= a ** 2:
        if n % a == 0:
            n //= a
            d.append(a)
        else:
            a += 1
    d.append(n)
    return d

def main():
    N = I()

    i = math.ceil(math.sqrt(N))
    while N % i != 0:
        i -= 1

    print(i + N//i - 2)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
i = 1
X = 1
ans = N - 1
while X <= N:
  if N % i == 0:
    ans = i + (N // i) - 2
  X = X + i + i + 1
  i += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

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

Submission status: Accepted

Solution code:
n = int(input())
root = int(n**0.5)
a = 0

for i in range(root, 0, -1):
  if n % i == 0:
    a = i
    break

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

Submission status: Accepted

Solution code:
n = int(input())
root = int(n**0.5)

yakusu = 0

for i in range(root, 0, -1):
  if n % i == 0:
    yakusu = i
    break

another = n // yakusu

print(yakusu + another - 2)

Submission status: Accepted

Solution code:
n=int(input())

def divisor(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

a=divisor(n)
a.sort()

c=[]
for i in range(len(a)//2+1):
    d=a[i]-1+a[-i-1]-1
    c.append(d)

print(min(c))

Submission status: Accepted

Solution code:
n=int(input())

def divisor(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

a=divisor(n)
a.sort()

b=sorted(a,reverse=True)

c=[]
for i in range(len(a)//2+1):
    d=a[i]-1+b[i]-1
    c.append(d)

print(min(c))

Submission status: Accepted

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

div_num = []
for i in range(1,int(math.sqrt(N))+1):
    if N%i== 0:
        div_num.append((i,N//i))
if div_num == []:
    div_num = [(1,N)]
min_div_num = 10**12
for i in div_num:
    min_div_num = min(sum(i),min_div_num)
print(min_div_num-2)

Submission status: Accepted

Solution code:
n=int(input())
import math
ans=10**12
i=0
while i*i<=n:
  i+=1
  if n%i!=0:
    continue
  j=n/i
  ans=min(ans, i+j-2)
if ans ==10**12:
  print(n-1)
else:
  print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())
i = 1 
res =N
flag = True
if N ==1:
  print(0)
else:
  k = int(N**0.5)
  for j in range(1,k+1):
    k = N / j
    b = int(k)
    if k-b == 0:
      res = min(res,j+b-2)
print(res)

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

Submission status: Accepted

Solution code:
import math

def some():
    n = int(input())
    y = int(math.sqrt(n))
    data = [(i+n//i)-2 for i in range(y, 0, -1) if n%i==0]
    print(min(data))

some()

Submission status: Accepted

Solution code:
n = int(input())
A = []
for i in range(1,int(n**0.5)+1):
    if n%i==0:
        if n//i!=i:
            A.append((i,n//i))
        else:
            A.append((i,i))
ans = float('inf')
for a,b in A:
    a-=1
    b-=1
    ans = min(ans, a+b)
# print(A)
print(ans)

Submission status: Accepted

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

for x in range(end, 0, -1):
    if n % x == 0:
        low = x
        break

high = int(n/low)
ans = low + high -2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

        if x < ans:
            ans = x

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N = int(input())

# 約数全列挙
def divisors(n):
    i = 1
    ans = []
    while i*i <= n:
        if n % i == 0:
            ans.append(i)
            if i*i != n: ans.append(n // i)
        i += 1
    ans.sort()
    return ans

a = divisors(N)
m = len(a)

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

Submission status: Accepted

Solution code:
from math import sqrt as r
from math import floor

N = int(input())

ans = 10 ** 20

for i in range(1, floor(r(N)) + 1, 1):
    if N % i == 0:
        a = i - 1
        b = (N // i) - 1
        ans_ = a + b
        ans = min(ans, ans_)

print(ans)

Submission status: Accepted

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

a.sort()
print(a[0])

Submission status: Accepted

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


n = int(input())
divs = make_divisors(n)
ans = 10**12
for div in divs:
    x = n // div
    ans = min(x - 1 + div - 1, ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())

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

print(int(p+N/p)-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
import math
y = int(math.sqrt(N))
ans = 10 ** 12

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

ans = []
i = 1
while i * i <= N:
    if N % i == 0:
        x = i
        y = N / i
        ans.append(x+y-2)
    i += 1
print(int(min(ans)))

Submission status: Accepted

Solution code:
N = int(input())
ans = N - 1
p = 1
for i in range(2, int((N ** 0.5) + 1)):
    if p % 2 == 1 and i > (N ** 0.5):
        break
    if N % i == 0:
        p = i
        j = N // i
        m = i + j - 2
        if m < ans:
            ans = m
        else:
            continue
    else:
        continue
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#nの約数を列挙する関数
import math
def n_div(n):
    div_list = []
    import math
    for i in range(1, math.ceil(math.sqrt(n))+1):
        if n % i ==0:
            div_list.append(i)
            if i*i ==n:
                continue
            div_list.append(n//i)
    div_list.sort()
    return div_list

n = int(input())
lr = n_div(n)
#print(lr)
if len(lr) % 2==0:
    a = len(lr)/2
    a = int(a)
    ans = lr[a]+lr[a-1]-2
else:
    a = math.floor(len(lr)/2)
    #print(a)
    ans = lr[a]*2  -2
    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass

n = int(input())

li = divisor(n)

l = len(li)

if l%2 == 1:
    ans = li[l//2] * 2 -2
else:
    ans = li[(len(li)//2)] + li[(len(li)//2)-1] - 2

print(ans)

Submission status: Accepted

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

i=1
ans=10**20

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

Submission status: Accepted

Solution code:
import math
def main():
  N = int(input())
  s = 0
  if N % 2 == 0:
    s = 2 + N // 2

  for i in range(3, math.ceil(math.sqrt(N)) + 3):
    if N % i == 0 and (not s or s > i + N // i):
      s = i + N // i

  if not s:
    s = N + 1

  print(s-2)
  
main()

Submission status: Accepted

Solution code:
import math
N = int(input())
ans = N - 1 #初期値、√Nの中に答えがなかったときはこれ
t = int(math.ceil(N**0.5))

for i in range(1,t+1):
    j = N / i
    if N % i == 0:
        step = i + j -2
        if step < ans:
            ans = int(step)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

divs = {}
ans = float('inf')

for i in range(1,int(n**(1/2))+1):
    if n%i == 0:
        a = i
        b = n//i
        tmp = a+b-2
        if tmp < ans:
            ans = tmp
print (ans)

Submission status: Accepted

Solution code:
n=int(input())
#i+j-2=cnt & i*j=n
minn=n+2
i=1
while i**2<=n:
    if n%i==0:
        j=n/i
        minn=min(int(i+j-2),minn)
    i+=1
print(minn)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import product, combinations,permutations
from copy import deepcopy
import sys
from math import sqrt
sys.setrecursionlimit(4100000)



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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
ans = 10**100

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

print(ans)

Submission status: Accepted

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

ans = math.inf
y = int(math.sqrt(N))

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

ans = make_divisors(N)
result = []
if len(ans)%2 == 0:
    for i, j in zip(range(0, int(len(ans)/2)), reversed(range(int(len(ans)/2), len(ans)))):
        result.append(int(ans[i]+ans[j])-2)
else:
    x = ans[int(len(ans)/2)]
    result.append((x-1)*2)
print(min(result))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

print(i+N//i-2)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
from math import sqrt
n=int(input())
def make_divisors(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]
l=make_divisors(n)
if len(l)%2==0:
	print((l[len(l)//2]+l[(len(l)//2)-1])-2)
elif len(l)%2==1:
	print(int((sqrt(n)*2)-2))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
ans = 10**18

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

Submission status: Accepted

Solution code:
import math
n = int(input())
i = 1
tmp = n-1
while i <= math.sqrt(n):
    if n%i == 0:
        j = n//i
        if i + j < tmp:
            tmp = i + j -2
        else:
            pass
    else:
        pass
    i += 1
print(tmp)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
yaku = make_divisors(n)

Min = float('inf')
for i in range(math.ceil(len(yaku)/2)):
    Min = min(Min, yaku[i]+yaku[-(i+1)])

print(Min-2)

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
divisors = make_divisors(n)
#print(divisors)
if len(divisors)%2==1:
    print(divisors[len(divisors)//2]*2-2)
else:
    m = len(divisors)//2
    print(divisors[m-1]+divisors[m]-2)

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
x = int(N**(0.5)) + 1
while True:
    if N % x == 0:
        print((x-1)+((N//x)-1))
        break
    x -= 1

Submission status: Accepted

Solution code:
N = int(input())
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
yakusulist = make_divisors(N)
center1 = yakusulist[(len(yakusulist)-1)//2]
center2 = yakusulist[(len(yakusulist))//2]
print(center1+center2-2)

Submission status: Accepted

Solution code:
n = int(input())
min_val = 10 ** 12 + 1
i = 1
while i * i <= n:
    if n % i == 0:
        j = n // i
        val = i + j
        if min_val > val:
            min_val = val
    i += 1
print(min_val - 2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
diff_min = pow(10, 12)
for a in range(1, n + 1):
    if n % a == 0:
        b = n // a
        diff = a + b - 2
        diff_min = min(diff_min, diff)
    if a * a > n:
        break
print(diff_min)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
    
n=int(input())
lis=make_divisors(n)
#print(lis)
ans=float('inf')
l=len(lis)
for i in range(l//2):
    ans=min(ans,lis[i]+lis[-1*(i+1)]-2)
if l%2:
    ans=min(ans,2*(lis[l//2]-1))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-08-08 22:05:18 +0900
# LastModified: 2020-08-09 00:49:47 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from math import sqrt


def prime_factor(n, prime_factor):
    for i in range(2, int(sqrt(n))+1):
        if n % i == 0:
            prime_factor.append(i)

def main():
    n = int(input())
    prime_list = []
    prime_factor(n, prime_list)
    if not prime_list:
        print(n-1)
        return
    i = prime_list[-1]
    j = n//i
    print(i-1+j-1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

m = pow(10, 12)

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

print(m)

Submission status: Accepted

Solution code:

n=int(input())
if int(n**(0.5))==n**(0.5):
    print(2*int(n**0.5)-2)
else:
    m=int(n**(0.5))
    i=m
    while not n%i==0:
        i-=1
    print(i+n//i-2)

Submission status: Accepted

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

import bisect

N=int(input())
list1=divisor(N)
list1=sorted(list1)
value1=(N**0.5)//1
num=bisect.bisect_left(list1,value1)

x=list1[num]
print(int(x+N/x-2))

Submission status: Accepted

Solution code:
x=int(input())
def divisors(n):
    lower_divisors=[]
    upper_divisors=[]
    i=1
    while i*i<=n:
        if n%i==0:
            lower_divisors.append(i)
            if i!=n//i:
                upper_divisors.append(n//i)
        i+=1
    return lower_divisors
max_lower_div=max(divisors(x))
print((max_lower_div-1)+(x//max_lower_div-1))

Submission status: Accepted

Solution code:
x=int(input())

for i in range(int(x**.5),0,-1):
    if x%i==0: break
print(i+x//i-2)

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())

t1 = 1

for i in range(2, int(math.sqrt(N)) + 1):
    if N % i == 0:
        t1 = i

t2 = N // t1

print(t1 + t2 - 2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


n = int(input())
divisors_list = make_divisors(n)
ans = []
n_sqrt = math.sqrt(n)
if n_sqrt == int(n_sqrt):
    for i in range(len(divisors_list) // 2 + 1):
        move = divisors_list[i] + divisors_list[-1 - i] - 2
        ans.append(move)
else:
    for i in range(len(divisors_list) // 2):
        move = divisors_list[i] + divisors_list[-1 - i] - 2
        ans.append(move)
print(min(ans))

Submission status: Accepted

Solution code:
from math import isqrt

N = int(input())

for x in range(isqrt(N), 0, -1):
    if not N % x:
        print(x + N // x - 2)
        exit()

Submission status: Accepted

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

n = int(math.sqrt(N))

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

print(int(min(l)))

Submission status: Accepted

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

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

print(min(A))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
p = 1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

res = 0
for i in range(int(N**0.5)):
    if(N % (i+1) == 0):
        res = max(res, i+1)

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

Submission status: Accepted

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

    ans = N - 1

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
from math import sqrt, ceil
for i in range(1, ceil(sqrt(n)) + 1):
    if n % i == 0:
        ans = i

print(ans-1 + (n//ans)-1)

Submission status: Accepted

Solution code:
n=int(input())
ro=n**0.5
# print( ro )

maxi=1
for i in range(2, int(ro)+1):
    if n%i==0:
        maxi=i

print( maxi-1+n//maxi-1)

Submission status: Accepted

Solution code:
def resolve():
    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)
    min_pair = 10**19
    for i in divisors:
        pair_i = n//i
        min_pair = min(min_pair, ((i-1)+(pair_i-1)))
    print(min_pair)
resolve()

Submission status: Accepted

Solution code:
import math


def isPrime(x):
    if x == 2:
        return True
    if x < 2 or x % 2 == 0:
        return False
    for i in range(3, int(x ** 0.5) + 1, 2):
        if x % i == 0:
            return False
    return True


def enum_div(n):
    ldv, udv = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            ldv.append(i)
            if i != n // i:
                udv.append(n // i)
        i += 1
    return ldv + udv[::-1]


n = int(input())
cnt = math.inf

if isPrime(n):
    cnt = n - 1
else:
    arr = enum_div(n)
    for i, v in enumerate(range(len(arr) - 1, -1, -1)):
        cnt = min(cnt, arr[i] + arr[v] - 2)

print(cnt)

Submission status: Accepted

Solution code:
import sys

INF = 10**60

inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inm())
instr = lambda: sys.stdin.readline()
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n = inint()

min_sum = INF

i = 0
j = 0

for k in range(1,n):
    if k > n**0.5:
        break
    if n/k % 1 != 0:
        continue
    i = k
    j = n/k
    if i+j < min_sum:
        min_sum = i+j

print(int(min_sum - 2))

Submission status: Accepted

Solution code:
N=int(input())
import math
n=int(math.sqrt(N))
m=0
T=True
while T==True:
  if N%n==0:
    m=N//n
    T=False
    break
  else:
    n-=1
print(n+m-2)

Submission status: Accepted

Solution code:
# ABC144 C - Walk on Multiplication Table
n = int(input())
m = n
for i in range(1,int(n**0.5)+1):
        if n%i==0:
            m = min(i+n/i-2,m)
print(int(m))

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def min2(x,y):
    return x if x < y else y

N = int(input())
P = make_divisors(N)
L = len(P) + 1
res =float("inf")

for p in P:
    res = min2((p - 1) + (N // p - 1), res)

print(res)

Submission status: Accepted

Solution code:
N = int(input())

n_hoge = int(N ** 0.5)
print

true_ans = 10 ** 12
for i in range(1,n_hoge+1):
    if N % i == 0:
        ans = N // i
        true_ans = min(ans + i - 2, true_ans)

print(true_ans)

Submission status: Accepted

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

Submission status: Accepted

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

	i += 1
print(ans)

Submission status: Accepted

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