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 math

N = int(input())

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

a = box[-1]
b = int(N / a)

kkk = (a-1) + (b-1)

print(kkk)

Submission status: Accepted

Solution code:
import math

N=int(input())

r=int(math.sqrt(N))

for i in reversed(range(1,r+1)):
    if N%i==0:
        x=i
        y=N//i
        break

print(x+y-2)

Submission status: Accepted

Solution code:
N=int(input()); j=N
a,b=0,0
for dx in range(0,1000000):
    i=1+dx
    tmp=N//i
    if i*tmp==N and (dx+tmp)<(a+j):
        j=tmp; a=dx
print(a+j-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)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

n = int(input())

d = make_divisors(n)
# print(d)
ans = n
for i in d:
    ans = min(ans, n//i - 1 + i - 1)
print(ans)

Submission status: Accepted

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

nr=int(n**0.5)


for i in range(1,nr+1):
    if n%i==0:
        ans.append(i+n//i)
   
ans2=sorted(ans)
print(ans2[0]-2)

Submission status: Accepted

Solution code:
import math

N = int(input())

A = math.sqrt(N)
B = math.floor(A)

while B > 0:
    if N % B == 0:
        C = [B, N/B]
        break
    B -= 1

D = int(C[0]+C[1]-2)

print(D)

Submission status: Accepted

Solution code:
n = int(input())

def divisors(n):
    ret = set()

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

div_lis = sorted(list(divisors(n)))

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

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
x = int(math.sqrt(n))
y = 2 if n % 2 == 0 else 1

for i in range(3, x + 1):
	if n % i == 0:
		y = n // i

print(y + (n // y) - 2)

Submission status: Accepted

Solution code:
import fractions

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)
sum = 0
#print(len(divisors))
sort_divisors = sorted(divisors)

if len(divisors) % 2 == 0:
  min1 = sort_divisors[int(len(divisors)/2)-1]
  min2 = sort_divisors[int(len(divisors)/2)]
else:
  min1 = sort_divisors[int((len(divisors)-1)/2)]
  min2 = min1

print(min1+min2-2)

Submission status: Accepted

Solution code:
import math
a = int(input())
b=round(math.sqrt(a))
check = True
while check:
    if a % b == 0:
        check = False
        c = [b,a/b]
    else:
        b -= 1
print(int(b-1+a/b-1))

Submission status: Accepted

Solution code:
import math
n = int(input())
sn = int(math.sqrt(n)) + 1

seki = []
for i in range(1, sn):
    if n%i == 0:
        seki.append([i, n//i])
totalseki = [sum(li) for li in seki]
min_ = min(totalseki)

print(min_ - 2)

Submission status: Accepted

Solution code:
N = int(input())
def divisor_list(num):
  ans = []
  for i in range(1, int(num**0.5)+1):
    if num % i == 0:
      ans.append(i)
      if i != num // i:
        ans.append(num//i)
  return ans
d_list = sorted(divisor_list(N))
ans = 10**12
for i in d_list:
    if ans > i+N//i-2:
      ans = i+N//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)

    # divisors.sort()
    return divisors

l = make_divisors(n)
x = n // l[-1]
print(x + l[-1]-2)

Submission status: Accepted

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

print(divisor(int(input())))

Submission status: Accepted

Solution code:
N = int(input())
import numpy
q = int(numpy.sqrt(N))
for i in range(q):
    if N%(q-i)==0:
        print(int(q-i-1 + N/(q-i)-1))
        break
    else:
        pass

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

w = 0

def make_div(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 = sorted(divisors)
    return divisors

min_div = make_div(n)

if len(min_div) == 2:
    print(n - 1)
else:
    w = min_div[len(min_div)//2] - 1
    h = n // min_div[len(min_div)//2] - 1
    print(w + h)

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


l = make_divisors(N)
answer = 10 ** 12

for i in l[:len(l) // 2 + 2]:
    answer = min(answer, i + N // i - 2)

print(answer)

Submission status: Accepted

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

n = int(input())

div_list = divisor(n)
list.sort(div_list, reverse=True)
x = div_list[0]
y = n / x


print(int(x-1+y-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)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

num = int(input())

divisors = make_divisors(num)

min = float('inf')

for n in reversed(divisors):
    temp = num / n
    temp_result = (n-1) + (temp-1)
    if temp_result < min:
        min = temp_result

print(int(min))

Submission status: Accepted

Solution code:
import math

N = int(raw_input())
mov = N-1

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

print(mov)

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())
i, j = 1, 1
l = make_divisors(N)
len_l = len(l)
if len_l % 2 == 1:
    idx = int((len_l-1)/2)
    print((l[idx]-i) + (l[idx]-j))
else:
    idx = int(len_l / 2)
    print(sum(l[idx-1:idx+1])-2)

Submission status: Accepted

Solution code:
import sys
import math

N = int(input())
sqrt = math.sqrt(N)

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


print(min(a[0] + a[1] -2 for a in ls))

Submission status: Accepted

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

N = int(input().split()[0])


def get_divisor(n: int) -> list:
    d_list = []
    for i in range(1, int(n ** (1 / 2)) + 1):
        if n % i == 0:
            a = int(n / i)
            d_list.append((i, a))
    return d_list


min_d = float("inf")

for d_set in get_divisor(N):
    x, y = d_set
    min_d = min(abs(1 - x) + abs(1 - y), min_d)

ans = min_d
print(ans)

Submission status: Accepted

Solution code:
import math
n = input()
n = int(n)
spl_list = [1]
for i in range(1,round(math.sqrt(n)) + 1):
  if n % i == 0:
    spl_list.append(i)

max_i = max(spl_list)
max_j = n / max_i
print(round(max_i + max_j -2))

Submission status: Accepted

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

def Main(n):
    fl = math.floor(math.sqrt(n))
    a = b = 0
    for i in range(fl, 0, -1):
        if(n % i == 0):
            a = n // i
            break
    b = n // a
    return a + b - 2   

def main():
    N = int(input())
    print(Main(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

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


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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sqN = math.floor(math.sqrt(N))
yaku1 = 1
yaku2 = 1
for i in range(sqN, 0, -1):
    if N % i == 0:
        yaku1 = i
        yaku2 = N // i
        break

print(yaku1+yaku2-2)

Submission status: Accepted

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

min_num = 1000000000000000000000
for i in range(int(math.sqrt(N))):
    if N%(i+1) == 0:
        root = (i+1)+(N/(i+1))-2
        if min_num > root:
            min_num = root
print(int(min_num))

Submission status: Accepted

Solution code:
import math

n=int(input())
minx,miny=0,0

for i in range(math.floor(n**0.5),1,-1):
    if n%i==0:
        minx=i
        miny=n//i
        break
else:
    minx=n
    miny=1


timestep=minx+miny-2
print(timestep)

Submission status: Accepted

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

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

    divs = trial_division(N)
    d = len(divs)
    ans = float('inf')
    for i in range(d):
        for j in range(i, d):
            if divs[i] * divs[j] == N:
                ans = min(ans, divs[i] - 1 + divs[j] - 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def get_div_list(num):
    if num == 1:
        return [1]
    else:
        div_list = []
        div_list.append(1)
        div_list.append(num)
        for i in range(2, math.floor(math.sqrt(num))+ 1):
            if num % i == 0:
                div_list.append(i)
                div_list.append(num // i)
        list(set(div_list))
        div_list.sort(reverse = True)
        return div_list
n=int(input())
l=get_div_list(n)
ans=10**15
for i in range(len(l)):
    if l[i] < n//l[i]:break;
    ans=min(abs(l[i]-1)+abs(n//l[i] -1),ans)
print(ans)

Submission status: Accepted

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

print(curmin-2)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]


N = int(input())
cnt = 0
n = N//2+1
k = int(N**0.5)+1
b = 0
for i in range(k,1,-1):
    if N%i==0:
        b = N//i
        a = i
        print(a+b-2)
        exit()
else:
    print(N-1)

Submission status: Accepted

Solution code:
import math

N = int(input())

a, b = N, 1
for i in range(math.ceil(math.pow(N, 0.5)), 1, -1):
    if N % i == 0:
        a = i
        b = N / i
        break

print(int(a + b - 2))

Submission status: Accepted

Solution code:
n = int(input())

import sys
import math

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

for i in range(_max, 1, -1):
    if n % i == 0:
        a = n // i
        b = i
        print((a-1) + (b-1))
        sys.exit(0)

print(n - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

import math

rtN = math.sqrt(N)
M = int(rtN)

for i in range(M,0,-1):
    if N % i == 0:
        res = [i,N//i]
        break

ans = res[0] + res[1] -2

print(ans)

Submission status: Accepted

Solution code:
# coding : utf-8

import numpy

n = int( input() )

lim_j = int(numpy.sqrt(n))

#素数判定
flag = True
for i in range(1, lim_j+1)[::-1]:
    if( n % i == 0 ):
        flag = False
        x = i
        y = int(n/i)
        break
if flag:
    print(n-1)
else:
    print( (x-1) + (y-1) )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue
from heapq import heappop, heappush
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
res = 10**13+4
for i in range(1,2*10**6):
    if (n/i).is_integer():
        res = min(res, i + n/i)
print(int(res-2))

Submission status: Accepted

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

import math
def main():
    N = int(input())
    left = 0
    right = 0
    
    if is_prime(N):
        print(N-1)
        return
    
    minimum_distance = 10 ** 12
    for i in range(1, int(N**0.5)+1):
        right = 0
        left = 0
        if N % i == 0:
            right = i
            left = math.floor(N/i)
            distance = (left - 1) + (right - 1)
            if minimum_distance > distance:
                minimum_distance = distance
        
    print(minimum_distance)
        
    
    

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import sqrt
N = int(input())
d = []
ans = 10 ** 12 + 1
for i in range(1,int(sqrt(N)+1)):
    if N % i == 0:
        d.append((i, int(N / i)))
for i in d:
    x, y = i
    cnt = x - 1 + y - 1
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

x = one_divide(N)
y = int(N/x)
print(x+y-2)

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

n = INT()

divs = divs(n)

res = divs[len(divs)//2 -1] + divs[len(divs)//2] -2

print(res)

Submission status: Accepted

Solution code:
# coding: utf-8
import math

N = int(input())

n = int(math.sqrt(N))

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

print(int(M))

Submission status: Accepted

Solution code:
n = int(input())

def divisor(n: int) -> list:
    list_of_divisor = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            list_of_divisor.append(i)
            if i != n//i:
                list_of_divisor.append(n//i)
    list_of_divisor.sort()
    return list_of_divisor

li = divisor(n)
num = len(li)
if num % 2 == 0:
    # print(li[num//2-1], li[num//2])
    if li[num//2-1] == 1:
        print(li[num//2]-1)
    else:
        print((li[num//2-1]-1)+(li[num//2]-1))
else:
    print((li[num//2]-1)*2)

Submission status: Accepted

Solution code:
import sys
import random
import math

def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

def solve():
    N = int(input())
    if is_prime(N):
        print(N-1)
        sys.exit()
    
    sq = int(math.sqrt(N))
    for i in range(sq, 1, -1):
        if N % i == 0:
            print(i+N//i-2)
            sys.exit()

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

lim = int(math.sqrt(N))

x = 1
while True:
    if N % lim == 0:
        x = lim
        break
    lim = lim - 1

y = N // lim

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

Submission status: Accepted

Solution code:
n=float(input())

w=int(n**(1/2))
n=int(n)
a=int(w)
b=int(w)
while True:

    if n%w==0:
        a=w
        b=n/w
        break
    w -=1

ans=int((a-1)+(b-1))
print(ans)

Submission status: Accepted

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

    #divisors.sort()
    return divisors

n = int(input())
lis = make_divisors(n)
print(lis[-1]+n//lis[-1]-2)

Submission status: Accepted

Solution code:
import math

N = int(input())
root_N = math.sqrt(N)
root_N_int = int(root_N // 1)

if root_N.is_integer():
    n = root_N
    m = root_N
else:
    for i in range(root_N_int, 0, -1):
        if N % i == 0:
            n = N / i
            m = N / n
            break

ans = n + m -2

print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
D = int(input())

for i in reversed(range(1, int(D ** ( 1 / 2 )) + 1)):
    if D % i == 0:
        a = D // i
        if D==1:
            print('1')
        else:
            print(a + i - 2)
        break

Submission status: Accepted

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

N = int(input())
D = make_divisors(N)
L = len(D)
I = D[L//2]
J = N//I
C = (I+J)-2
print(C)

Submission status: Accepted

Solution code:
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append((i-1)+(n//i-1))
        i += 1
    table = list(set(table))
    a = min(table)
    return a

print(divisor(int(input())))

Submission status: Accepted

Solution code:
import math

n = int(input())

k = math.ceil(math.sqrt(n))

for i in reversed(range(k+1)):
  if n/i == n//i:
    print(int(n/i + i -2))
    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
div = make_divisors(N)
tmp = []
if len(div)%2 == 0:
    tmp.append(div[int(len(div)/2)])
    tmp.append(div[int(len(div)/2-1)])
else:
    tmp.append(div[len(div)//2])
    tmp.append(div[len(div)//2])
ans = 0
ans = sum(tmp)-2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

    # divisors.sort()
    return divisors

n = int(input())
count = make_divisors(n)
a = count[-1]
b = n//a
print(a+b-2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
def divisor_enumetarion(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())
    x=[n//i+i for i in divisor_enumetarion(n)]
    print(min(x)-2)
    
    
    
    
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

x=int(input())
a=make_divisors(x)
a.sort()
for i in range(len(a)):
    if a[i]>=x**0.5:
        print(a[i]+(x//a[i])-2)
        exit()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

minimum = 10**13
for u in range(1, int(n**0.5) + 1):
    if n % u == 0:
        cand = u + (n/u)
        if cand < minimum:
            minimum = cand
            i, j = u, n/u

print(int(i+j-2))

Submission status: Accepted

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

    ans = 2000000000000
    a = 1 + int(n**0.5)

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

    ans -= 2
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import math
N = int(stdin.readline().rstrip())
fact = 0
for i in range(1,math.ceil(math.sqrt(N))+1):
    if N % i == 0:
        fact = i

ans = fact + (N//fact) -2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


n = int(input())
tmp = int(math.sqrt(n)) + 1
result = n-1
for num in range(2, tmp):
    a = n // num
    b = n % num
    tmp_result = a + num - 2
    if (b==0) & (tmp_result < result):
        result = tmp_result

print(result)

Submission status: Accepted

Solution code:
import math
import sys

N = int(input())
ans = N

for k in range(2, int(math.sqrt(N)) + 1):
        if N % k == 0:
            if N//k + k < ans:
                ans = N//k + k
            #print(k-1 + N//k-1)
            #print(k,N/k)
            #sys.exit()
if ans == N:
    print(N-1)
else:
    print(ans-2)

Submission status: Accepted

Solution code:
from collections import Counter
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

div = make_divisors(n)
a = 10**12
for i in range( 0, len(div[:-1]), 2):
    a = min(a, div[i]+div[i+1])
if len(div) % 2 == 1:
    a = min(a, div[-1]*2)
print(a-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())
minimum = N+1
for i in make_divisors(N):
    if i + (N // i) <= minimum:
        minimum = i + (N // i)


print(minimum - 2)

Submission status: Accepted

Solution code:
import math

N = int(input())
x = int(math.sqrt(N))

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

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

Submission status: Accepted

Solution code:
n = int(input())
lim = n
i = 1

a = 1
b = n
while lim > i:
    if n % i == 0:
        if a + b > n % i + i:
            a = i
            b = n / i
    lim = n // i
    i += 1
sub = a + b - 2
'''
if a == 1:
    print("こっちに")
    sub += 1
if b == 1:
    print("きてる")
    sub += 1
'''
print(int(sub))

Submission status: Accepted

Solution code:
N=int(input())
k=int(N**(1/2))
i=k
while i>=1:
  if N/i == int(N/i):
    m=i
    break
  i=i-1
print(int(i+N/i-2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())


def dist(i, j):
    return i + j - 2


min = 10 ** 24
i = 1
while (i ** 2) <= N:
    if 0 == N % i:
        j = N // i
        d = dist(i, j)
        if min > d:
            min = d
    i += 1
print(d)

Submission status: Accepted

Solution code:
N=int(input())
a=-1
for i in range(1,1000001):
    if N%i==0:
        a=i-2+N//i
        if i>=N//i:
            break
if a!=-1:
    print(a)
else:
    print(N-1)

Submission status: Accepted

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

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

k = len(f_list)
for i in range(-(-k//2)):
  t = f_list[i]+f_list[k-i-1]

print(t - 2)

Submission status: Accepted

Solution code:
import math
N = int(input())
counter = N+N
upper = int(math.ceil(math.sqrt(N)))
for i in range(upper):
  List = []
  if N%(i+1)==0:
    List.append([i+1,int(N/(i+1))])
  for item in List:
    if item[0]+item[1]-2 < counter:
      counter = item[0]+item[1]-2
  
print(counter)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
ans_list = []
tasu = []
for i in range(1,n):

    if n%i == 0:
        ans_list.append([i,n//i])
        tasu.append(i+n//i)
    if i*i > n:
        break
ans = ans_list[tasu.index(min(tasu))]
print(ans[0] + ans[1]-2)

Submission status: Accepted

Solution code:
N = int(input())
A = int(pow(N, 0.5))

found = False
for a in range(A, 0, -1):
    #print(a)
    if N % a == 0:
        found = (a - 1) + (N // a - 1)
        break

print(found)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics

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=int(input())	
b=make_divisors(a)
x=statistics.median_low(b)


y=a/x

print(int(x+y-2))

Submission status: Accepted

Solution code:
import math

N = int(input())

for i in range(1, int(math.sqrt(N) + 1))[::-1]:
    if N % i == 0:
        print(i - 1 + N // i - 1)
        break

Submission status: Accepted

Solution code:
from math import sqrt

n=int(input())
count=[]

for i in range(1,int(sqrt(n))+1):
    if n%i==0:
        count.append(i+n/i)

print(int(min(count)-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

div = make_divisors(int(input()))
x = len(div)
if x % 2 == 1:
    print(div[x//2] * 2 - 2)
else:
    print(div[x//2 - 1] + div[x//2] - 2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N = int(input())

max_n = math.ceil(math.sqrt(N))

a = 0
b = 0

for i in range(max_n + 1, 0, -1):
    if N % i == 0:
        a = i
        break

b = N / a


print(str(int(a-1 + b-1)))