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())
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
#lst = prime_factorize(N)
lst = make_divisors(N)
lst.sort()
#print(lst)
if len(lst) == 2:
    print(lst[-1] - 1)
else:
    if len(lst) % 2 == 0:
        print(lst[len(lst)//2] + lst[len(lst) // 2 - 1] - 2)
    else:
        print(lst[len(lst) // 2] * 2 - 2)

Submission status: Accepted

Solution code:
N=int(input())
c=[]
d=[]
for i in range(1,10**8):
  if (N%i)==0 and (int(N/i)-i)>=0:
    c.append(int(N/i)-i)
    d.append(int(N/i))

for l in range(0,len(c)):
  if min(c)==c[l] and len(c)>1:
    m=N/d[l]
    print(int((m-1)+(d[l]-1)))
  elif len(c)==1:
    print(N-1)

Submission status: Accepted

Solution code:
import math


n = int(input())
ans_L = []
d = []
for val in range(int(math.sqrt(n)+1),0,-1):
    if n % val ==0:
        x = val
        y = int(n/val)
        #st = str(x) + "*" +str(y)
        #d.append(st) 
        #ans_L.append(int(x+y-2))
        print(int(x+y-2))
        exit()
#print(d)
#print(ans_L)
#print(min(ans_L))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

tmp = N-1

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

print(int(tmp))

Submission status: Accepted

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

root = math.floor(N ** (1/2))

while True:
    if N % root == 0:
        print(root + N // root - 2)
        break
    root -= 1

Submission status: Accepted

Solution code:
import math
n = int(input())
def yinzi(n):
    list_yinzi = []
    if n <= 2:
        return list_yinzi
    for i in range(2, int(math.sqrt(n)) + 1):
        """
        为什么循环范围定在平方根呢？：因为一个数的因子是成对的，a=b*c。也就是说：找到一个因子b，肯定会找到相对应的另外一个因子c（a/b）。所以我们的工作量减少了一半。
        又有：一个因子变大，另一个因子必然要变小。假设b永远是小的那个，c是大的那个，那么b的最大值就是a的平方根。也就是b=c=(根号a)的时候。所以循环范围定在[1 , a的平方根+1]，+1的原因是为了能够取到a的平方根避免遗漏。
        """
        #如果找到了一个因子，那么把其相对应的另一个因子一同加入到因子列表中
        if n % i == 0:
            list_yinzi.extend([i, n/i])

    #此处的set为了去重，因为会出现两个相同的平方根的情况。所以去掉重复
    #sorted重排序是因为，因子都是成对成对找出来的，也就是说一次找到的两个因子肯定会有一大一小。这样把所以因子找完放在一起，大小排序就乱了
    return sorted(set(list_yinzi))
res = []
if len(yinzi(n)) == 0:
    print(n-1)
else:
    for i in yinzi(n):
        res.append(i+n/i)
    print(int(min(res)-2))

Submission status: Accepted

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

    # divisors.sort()
    return divisors
N = make_divisors(a)
#print(N)
m = 10000000000000
for i in range(len(N)):
  if m > (a//N[i]-1) + (N[i]-1):
    m = (a//N[i]-1) + (N[i]-1)
    
print(m)

Submission status: Accepted

Solution code:
num_s = input()
num = int(num_s)

def check(num):
    n = []
    for i in range(1, int(num**0.5)+1):
        if i > num:
            break
        if (num % i == 0):
            n.append(i)
    return n
ans = check(num)
a = max(ans)
b = int(num / a)


a = a - 1
b = b - 1

print(a + b)

Submission status: Accepted

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

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 accum(s):
    value = 1
    for ss in s:
        value = value*ss
    return value

def solve(N: int):
    divisors = divisor(N)
    divisors.sort()
    answer = 10**12
    LEN = len(divisors)
    for i in range(0,LEN):
        seki = divisors[i]+divisors[LEN-1-i]
        answer = min(answer,seki)

    print(answer-2)
    return


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

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

if len(prime_factorize(n)) == 1:
  print(n - 1)
  exit()

ret = None
min_r = n
for x in range(2, int( n / 2)):
  q, mod = divmod(n, x)
  _min_r = (2 * x - 2) + (q - x)
  if mod == 0 and min_r > _min_r:
    min_r = _min_r
    ret = (x, q)
  
  if x > q:
    break

print(min_r)

Submission status: Accepted

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

    # divisors.sort()                                                          
    return divisors

a = np.sort(make_divisors(n))
#print(a)                                                                      
if len(a)//2==0:
    x = len(a)//2-1
else:
    x = len(a)//2

xx = a[x]
yy= n//xx

print(xx-1+yy-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import sqrt

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

Submission status: Accepted

Solution code:
n = int(input())

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

divisors.append(divisors[-1])

aaa = 0
bbb = 10**12+1
j = 0

for i in range(1,len(divisors)//2+1):
    aaa = divisors[j]+divisors[j+1]-2
    if aaa < bbb:
        bbb = aaa
    j += 2
    
print(bbb)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import sys
ans = 9223372036854775807
n = int(input())
a = list(range(1,math.ceil(math.sqrt(n))+1))
for i in a:
    s = n/i
    if s==int(s):
        ans = min(i+s-2,ans)
print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())

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

    divisors.sort()
    return divisors

yakusu = make_divisors(n)

answers = []
for i in range(len(yakusu)):
    answers.append(yakusu[i] + yakusu[-(i+1)] - 2)

print(min(answers))

Submission status: Accepted

Solution code:
n = int(input())

divs = []

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

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

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:
# C Walk on Multiplication Table
import math

def calc():
    #約数求める
    yakusuu_list = [1]
    for i in range(2, int(math.sqrt(N) + 1e-9) + 1):
        if N % i == 0:
            yakusuu_list.append(i)
            #if N != i**2:
            #    if N % i**2 == 0:
            #        yakusuu_list.append(i**2)
    
    yakusuu_list.append(N)

    min_walk = 10000000000000
    for yak in yakusuu_list:
        ans = N / yak
        walk = ans + yak
        if walk < min_walk:
            min_walk = walk
    
    final_ans = min_walk - 2
    print(int(final_ans))

if __name__ == "__main__":
    N = int(input())
    calc()

Submission status: Accepted

Solution code:
import math

N = int(input())
sum = N - 1
b = int(math.sqrt(N))
for i in range(2, b+1):
    if(N%i==0):
        if((N//i+i-2)<=sum):
            sum = N//i+i-2

print(sum)

Submission status: Accepted

Solution code:
n = int(input())

divs = []

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

max = len(divs) -1
print(divs[max] + divs[max-1] - 2)

Submission status: Accepted

Solution code:
def factorization(n):
    temp = n
    for i in range(int(-(-n**0.5//1)),0,-1 ):
        if temp%i==0:
            b = temp//i
            return i,b

a,b = factorization(int(input()))
print(a-1+b-1)

Submission status: Accepted

Solution code:
N = int(input())
# N = 10000000019


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

    # divisors.sort()
    return div

def get_center(l):
    if len(l) %2 == 0:
        return l[len(l) // 2 - 1] + l[len(l) // 2 ] - 2
    else:
        return l[len(l) // 2] * 2 - 2

a = sorted(make_div(N))
print(get_center(a))

Submission status: Accepted

Solution code:
N = int(input())

a = 0
b = 0

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

print(int(a + b - 2))

Submission status: Accepted

Solution code:
N = int(input())

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

    # divisors.sort()
    return divisors

d = make_divisors(N)
# print(d)

Ans_min = 1+N-2

for x in d:
  y = N/x
  Ans = x+y-2
  if Ans < Ans_min:
    Ans_min = Ans
    
print(int(Ans_min))

Submission status: Accepted

Solution code:
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.sort()
    # 偶数の場合
    if (len(divisors) + 1) % 2 == 1:
        x = (len(divisors) + 1) // 2 - 1
        ans1 = divisors[x] - 1 + divisors[x + 1] - 1
        print(ans1)
    # 奇数の場合
    else:
        y = len(divisors) // 2
        ans2 = 2 * (divisors[y] - 1)
        print(ans2)
    return divisors


m = int(input())
make_div(m)

Submission status: Accepted

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

if S%2 == 0:
  print(divisors[int((S/2)-1)] + divisors[int(S/2)] - 2)
else:
  print((divisors[int((S-1)/2)]-1)*2)

Submission status: Accepted

Solution code:
import math
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())
Nlist = make_divisors(N)
L = len(Nlist)
if L%2==0:
    print(Nlist[int(L/2)]+Nlist[int(L/2)-1]-2)
else:
    print(int(math.sqrt(N)*2-2))

Submission status: Accepted

Solution code:
N=int(input())
A=[]
B=[]
i=1
while True:
    if N/i>=i:
        if N%i==0:
            A.append(N/i)
            B.append(i)
        i+=1
    else:
        break
print(int(A[-1]+B[-1]-2))

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())

it = int(sqrt(N))

for i in range(it, 0, -1):
    remain = N % i
    if remain == 0:
        shou = N / i

        print(int(i+shou-2))
        break

Submission status: Accepted

Solution code:
import statistics
import math
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())
nums = make_divisors(n)
a = statistics.median_low(nums)
b = n / a
print(int(a+b-2))

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())
a=int(np.sqrt(N))
b=float('inf')
for i in range(1,a+1):
    if N%i==0:
        if i+N//i<b:
            ans=i

print(ans+N//ans-2)

Submission status: Accepted

Solution code:
n = int(input()) 

import math

def is_prime(n):
  for k in range(int(math.sqrt(n)) + 1,0,-1):
    if n % k == 0:
      print(int(k-1+n/k-1))
      break


is_prime(n)

Submission status: Accepted

Solution code:
import math
  
a = int(input())
rs = []

for i in list(range(1,math.floor(a**0.5) + 1)):
  q, mod = divmod(a, i)
  if mod == 0:
    rs.append([i, q])
  else:
    pass
  
print(sum(rs[len(rs) - 1]) - 2)

Submission status: Accepted

Solution code:
import heapq

N = int(input())

def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

fct = factorize(N)
steps = []
for div in divisorize(fct):
    a = num(div)
    b = N//a
    step = a+b-2
    steps.append(step)
    
heapq.heapify(steps)
print(heapq.heappop(steps))

Submission status: Accepted

Solution code:
import math
def main2():
    def get(N):
        res = set()
        for i in range(1, int(math.sqrt(N)+2)):
            if N % i == 0:
                res.add(i)
                res.add(N // i)
        return res
    N = int(input())
    mini = 10 ** 15
    for c in get(N):
        d = N // c
        e = c + d - 2
        mini = min(mini, e)
    print(mini)
main2()

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    maxVal = 10 ** 13
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            value = (temp//i) + i - 2
            if value < maxVal :
                maxVal = value
            #arr.append([i, n//i])
            #cnt=0
            #while temp%i==0:
            #    cnt+=1
            #    temp //= i
            #    arr.append(i)
            # arr.append([i, cnt])

    #if temp!=1:
    #    arr.append(temp)

    if maxVal == 10 ** 13:
        maxVal = n - 1

    return maxVal

n = int(input())
print(factorization(n))
'''
factList = factorization(n)

max = 10 ** 13
if len(factList) == 1 :
    print(factList[0] - 1)
    exit()
#factList = sorted(factList, reverse=True)
#print(factList)
pair = [1, 1]
#for i in range(len(factList)) :
#    if pair[0] <= pair[1] :
#        pair[0] *= factList[i]
#    else :
#        pair[1] *= factList[i]
#print(pair)
print(factList)
print(pair)
print(sum(pair) - 2)
'''

Submission status: Accepted

Solution code:
N = int(input())
'''
def factorization(n):
    arr = [1,1]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                if arr[1] >= arr[0]:
                    arr[0] = arr[0]*i
                else:
                    arr[1] = arr[1]*i
                temp //= i   
    if temp!=1:
        if arr[1] >= arr[0]:
            arr[0] = arr[0]*temp
        else:
            arr[1] = arr[1]*temp
    if arr==[1,1]:
        arr[0] =n
    return arr

facro = factorization(N)
print(facro[0] +facro[1] -2)
'''
min_num = 1
 
for i in reversed(range(2,int(-(-N**0.5//1))+1)):
    if N%i == 0:
        #print(i)
        min_num = i
        break

print(min_num + N//min_num-2)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
for i in range(int(np.floor(np.sqrt(n))), 0, -1):
    if n % i == 0:
        print(i + int(n / 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([n//i,i])

    # divisors.sort()
    
    return divisors

def resolve():

    a = int(input())
    divisors = make_divisors(a)
    anss= [] 
    for i in range(len(divisors)):
        anss.append(sum(divisors[i]))
    print(min(anss) - 2)

    
resolve()

Submission status: Accepted

Solution code:
N = int(input())

def factorization(n):
    arr = [[1,n]]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            c = temp // i
            arr.append([i, c])
    return arr

L = factorization(N)
distance = [l[0] + l[1] for l in L]

m = min(distance)
print(m-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

num = int(input())
yakusu_list = make_divisors(num)
nine = [1,2,3,4,5,6,7,8,9]
yakusu_pair_list = []
a = 0
b = 0
for i, yakusu in enumerate(yakusu_list):
    
    if len(yakusu_list) % 2 == 0:
        if i % 2 == 0:
            a = yakusu
        else:
            b = yakusu
            yakusu_pair_list.append([a, b])
    else:

        if i == len(yakusu_list) -1:
            yakusu_pair_list.append([yakusu, yakusu])
    
        else:
            if i % 2 == 0:
                a = yakusu
            else:
                b = yakusu
                yakusu_pair_list.append([a, b])
best_pair = yakusu_pair_list[0]
best_move_num = best_pair[0] + best_pair[1] -2
for yakusu_pair in yakusu_pair_list:
    this_move_num = yakusu_pair[0] + yakusu_pair[1] -2
    if this_move_num < best_move_num:
        best_pair = yakusu_pair    
        best_move_num = this_move_num
print(best_move_num)

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:
#                 x = (n//i)
#                 y = x + (n / x)
#                 divisors.append(y)
#
#     divisors.sort()
#     return divisors

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

t = make_divisors2(n)
li = []
for i in t:
    li.append(i + n / i)

print(int(min(li)-2))

Submission status: Accepted

Solution code:
def cal(n):
  min_num = -1
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      num = i + (n//i)
      if min_num < 0 or num < min_num:
          min_num = num
  return min_num -2
_ = int(input())
print(cal(_))

Submission status: Accepted

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

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

print(int(yaku2+yaku - 2))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections  import defaultdict
import bisect

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())
M=sorted(make_divisors(N))
p=bisect.bisect(M, N**0.5)
#print(p,M)
ans1=M[p]+(N//M[p])-2
ans2=9999999999999999999
ans3=9999999999999999999
if p>0:
    ans2=M[p-1]+(N//M[p-1])-2
if p<len(M)-1:
    ans3=M[p+1]+(N//M[p+1])-2
print(min(ans1,ans2,ans3))

Submission status: Accepted

Solution code:
n = int(input())
min = n+1
kaisu = int(n-1)

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

print(int(min))

Submission status: Accepted

Solution code:
import math

N = int(input())

ans = 10**13
flag = 0
nijou = math.sqrt(N)


for i in range(2,int(nijou +1e-9)+1):
    if N%i == 0:
        j = N//i
        
        if ans > (j-1)+(i-1):
            ans = (j-1)+(i-1)

        flag = 1

        
    else:
        continue

if flag == 0:
    ans = N-1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n = int(input())

ns = [int(i) for i in str(n)]
a = 0
b = 0
ans = 0
f = 0


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

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

# print('a',a)
# print('b',b)

if f:
    print(ans)
else:
    ans = a - 1 + b - 1
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a = int(input())
min_steps=a
if a==2:
    print(1)
elif a==3:
    print(2)
else:
    j=2
    while(1):
        if j*j>=a:
            break
        else:
            j+=1

    for i in range(2, j+1):
            if a%i==0:
                b=i+int(a/i)-2
                if b<min_steps:
                    min_steps=b
    if (min_steps==a):
        min_steps-=1
    print(min_steps)

Submission status: Accepted

Solution code:
n = int(input())

import math

k = int(math.sqrt(n))
t = n
q = 1

while k > 1:
    if n % k == 0:
        q = n//k
        t = int(k)
        break
    k -= 1

print(t+q-2)

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
n = int(input())						# 5

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

j=0
for i in range(a,0,-1):
	if n/i==int(n/i):
		j=int(n/i)
		#p(i,j)
		break

print(i-1+j-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n = int(input())
nr = int(math.sqrt(n))+1
ans = 0


for i in reversed(range(1,nr)):
    if n % i == 0:
        n //= i
        ans = i
        break


print(ans+n-2)

Submission status: Accepted

Solution code:
#%%
n = int(input())
a = 10**15


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

if a == 10**15:
    print(n-1)
else:
    print(a+b-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
 
if len(divisor(N)) < 3:
    print(N - 1)
else:
    divisor_list = divisor(N)
    tmp = N
    for i in divisor_list:
        A = i
        B = N / i
        if tmp > (A + B - 2):
            tmp = (A + B - 2)
    print(int(tmp))

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

if len(s)%2==0:
    k=int(len(s)/2) 
    ans=max((n/s[k]+s[k])-2,0)
    print(int(ans))
else:
    k=int(len(s)/2) 
    ans=min(n/s[k]+s[k]-2,n/s[k+1]+s[k+1]-2)
    print(int(ans))

Submission status: Accepted

Solution code:
import math
n = int(input())
flag = True
ans = n - 1
for i in reversed(range(2, int(math.sqrt(n))+1)):
  if (n%i == 0):
    ans = i + n//i - 2
    break
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())
a = (make_divisors(n))
ans = 100000000000000
for i in a:
  if(ans > i+int(n/i)-2):ans = i+int(n/i)-2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

n=int(input())
m=prime_factorize(n)
M=m[::-1]
#print(m)
if m==[n]:print(n-1)
else:
    a=int(n**(1/2))
    l=[]
    for i in range(1,a+1):
        if n%i==0:
            l.append(i)
    #print(l)
    ans=(l[-1]-1)+(n//l[-1]-1)
    print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

    divisors.sort()
    return divisors

def main():
    n = INT()
    lis = make_divisors(n)
    #print(lis)

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

if  __name__=='__main__':
    main()

Submission status: Accepted

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

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


divs = make_divisors(N)
if N // divs[len(divs) // 2] == divs[len(divs) // 2]:
    i = len(divs) // 2
else:
    i = len(divs) // 2 - 1
print(divs[i]-1 + N // divs[i]-1)

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))
    table = list(table)
    table.sort()
    return table

N = int(input())

#for N in range(1000000000000):
n = []
n = divisor(N)
#print(n)

cnt = 999999999999999
for i in range(0,len(n)//2,1):
    t = int(n[i])-1 + int(n[len(n)-i-1])-1
    if cnt > t:
        cnt = t
print(cnt)

Submission status: Accepted

Solution code:
from math import sqrt, floor

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 main():
    N = int(input())

    # x = prime_factorize(N)
    # D = []
    # for i in range(2 ** len(x)):
    #     a = format(i, '0{}b'.format(len(x)))
    #     D.append(a)

    # mn = 1 + N
    # for di in D:
    #     a = 1
    #     b = 1
    #     for i, dii in enumerate(di):
    #         if dii == '0':
    #             a = a * x[i]
    #         else:
    #             b = b * x[i]
    #     mn = min(mn, a + b)
    # print(mn - 2)

    NN = floor(sqrt(N))
    mn = N + 100
    for i in range(1, NN + 1):
        if N % i == 0:
            a = i
            b = N // i
            # print(a, b)
            mn = min(mn, a + b)

    print(mn - 2)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
i = 1
min = 9000000000000
for _ in range(1, int(math.sqrt(N)+1)):
  if N % i == 0:
    j = N/i
    sum = j + i
    if sum < min:
      min = sum
      ans = i-1+j-1
    else:
      break
  i += 1
print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())

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

key_list = make_divisors(n)
ans = 10000000000000
for value in key_list:
    key = value + n//value - 2
    if key < ans:
        ans = key
print(ans)

Submission status: Accepted

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