Problem:


Score : 300 points

Problem Statement

Takahashi is standing on a multiplication table with infinitely many rows and columns.

The square (i,j) contains the integer i \times j. Initially, Takahashi is standing at (1,1).

In one move, he can move from (i,j) to either (i+1,j) or (i,j+1).

Given an integer N, find the minimum number of moves needed to reach a square that contains N.

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the minimum number of moves needed to reach a square that contains the integer N.

Sample Input 1

10

Sample Output 1

5

(2,5) can be reached in five moves. We cannot reach a square that contains 10 in less than five moves.

Sample Input 2

50

Sample Output 2

13

(5, 10) can be reached in 13 moves.

Sample Input 3

10000000019

Sample Output 3

10000000018

Both input and output may be enormous.



Sample input:
10


Sample output:
5

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    N=ii()
    x=int(N**0.5)
    while x>0:
        y=N//x
        if x*y==N:
            print(x+y-2)
            exit()
        else:x-=1


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
input = sys.stdin.readline
N= int(input())
M = int(N**(1/2))
ans = 1
for i in range(1,M+1):
    if N%i == 0:
        ans = i
print(ans+N//ans-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


def solve_c(c):
    res = c - 1
    d = math.floor(math.sqrt(c))
    for a in range(2, d + 1):
        if c % a == 0:
            res = (a - 1) + (c // a - 1)
    return res


def main():
    # input
    c = int(input())
    res = solve_c(c)
    print(res)


def test():
    assert solve_c(10) == 5
    assert solve_c(50) == 13
    assert solve_c(10000000019) == 10000000018


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
N = int(input())
k = 0
while k ** 2 < N:
  k += 1
for i in range(k, 0, -1):
  if N % i:
    continue
  print(N // i + i - 2)
  break

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            yield n // i

@mt
def slv(N):
    d = [n for n in divisor(N)]
    x = d.pop()
    y = d.pop()
    return (x-1) + (y-1)


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n = int(input())
q = int(math.sqrt(n))
result = n - 1

for i in range(q):
    c = q - i
    if n % c == 0:
        result = c + n // c - 2
        break

print(result)

Submission status: Accepted

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


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


def main():
    N = int(input())
    D = make_divisors(N)
    mi = N
    for d in D:
        mi = min(mi, d + (N//d) - 2)
    print(mi)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input().strip())

rt = int(N**0.5)

for i in range(rt, 0, -1):
    if N % i == 0:
        j = N//i
        i = i-1
        j = j-1
        print((i+j))
        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

divisors = make_divisors(N)

min_sum = 0

for A in divisors:
    B = N // A
    if min_sum == 0 or A+B <= min_sum:
        min_sum = A+B
print(min_sum-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def calc_divisore(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=calc_divisore(n)
if len(d)%2==0:
    print((d[len(d)//2]+d[(len(d)//2)-1]-2))
else:
    print((d[len(d)//2]*2)-2)

Submission status: Accepted

Solution code:
import math

def solve():
  N = int(input())
  for i in range(math.floor(math.sqrt(N)), 0, -1):
    if N % i != 0: continue
    return i + (N // i) - 2

print(solve())

Submission status: Accepted

Solution code:
from math import sqrt,ceil

N = int(input())

for x in reversed(range(ceil(sqrt(N))+1)):
    if N%x == 0:
        print(x+N//x-2)
        break

Submission status: Accepted

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

M = int(math.sqrt(N))

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

print(N-1)

Submission status: Accepted

Solution code:
n=int(input())
ans=10**15
for i in range(1,int(n**0.5)+2):
  if n%i!=0:continue
  check=(n//i)+i
  if ans>check-2:
    ans=check-2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from math import sqrt

n= int(sys.stdin.readline().strip())
ans = n-1
for i in range(int(sqrt(n)),0,-1):
    if n%i==0:
        ans = i + n//i - 2
        break
#
print(ans)

Submission status: Accepted

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

from math import sqrt, floor

def readInts():
  return [int(s) for s in input().split(" ")]

def solve(N):
  ans = N - 1
  for i in range(1, floor(sqrt(N)) + 1):
    if N % i == 0:
      ans = min(ans, (i - 1) + ((N // i) - 1))
  return ans

def main():
  N = readInts()[0]
  print(solve(N))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
N = int(input())

def make_divisors(n):
    divisors = []
    # Nの最大の約数は√N
    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

m = 10**12
divs = make_divisors(N)
for d1 in divs:
    d2 = N // d1
    m = min(m, d1+d2-2)
print(m)

Submission status: Accepted

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

Submission status: Accepted

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

ans = []

for i in range(1,10**6+1):
  if N % i == 0:
    ans += [i + N//i - 2]

print(min(ans))

Submission status: Accepted

Solution code:
N = int(input())

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

print(ans-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())
a = make_divisors(N)[-1]
b = N // a
print(a + b - 2)

Submission status: Accepted

Solution code:
n = int(input())
a = int(n**0.5)+1
for v in range(a,0,-1):
    q,r = divmod(n,v)
    if r==0:
        print(q+v-2)
        break

Submission status: Accepted

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

    ans = n - 1

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


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

import math

root=int(math.sqrt(n))
ans=float("inf")

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

Submission status: Accepted

Solution code:
a = int(input())


def m(n):
    res = []
    m = 1000000000010
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
#             divisors.append(i)
#             divisors.append(n//i)
            s = i + n//i
#             res.append(s)
            m = min(s,m)

    # divisors.sort()
    return m
print(m(a)-2)

Submission status: Accepted

Solution code:
N=int(input())

ans=10**12
for i in range(1,N):
  if i>10**6:
    break
  
  if N%i==0:
    A=i
    B=N//i
    if A+B-2<ans:
      ans=A+B-2
      
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

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 main():
    n = int(input())
    ans = float("inf")
    for i in range(1,1000001):
        if n % i == 0:
            ans = min(i-1 + n//i-1,ans)
    print(ans)





    
            
    

    

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def fact(n):
    l=set()
    x=1
    while(x*x<=n):
        if(n%x==0):
            l.add(x)
            l.add(n//x)
        x+=1
    l=list(l)
    l.sort()
    return l
n=int(input())
l=fact(n)
#print(l)
ans=10**12
i=0
j=len(l)-1
while(i<j):
    ans=min(ans,l[i]-1+l[j]-1)
    i+=1
    j-=1
if(len(l)%2==1):
    ans=min(ans,l[len(l)//2]-1+l[len(l)//2]-1)
print(ans)

Submission status: Accepted

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

    # calc
    ans = 10**13
    for i in range(1, int(n**0.5)+1):
        num = n / i
        if num - int(num) == 0:
            ans = min(ans, i+num-2)
    print(int(ans))

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

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

# coding: UTF-8
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 = readi()
mn = -1
for i in make_divisors(n):
    p = i - 2
    t = n // i
    p += t
    if mn == -1:
        mn = p
    mn = min(mn, p)
print(mn)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
import math
N = int(input())
for i in range(int(math.sqrt(N)), 0, -1):
    if N % i == 0:
        print(i + N // i - 2)
        exit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)


def main():
    N = int(input())
    min_ = N - 1
    for i in range(1, int(N ** 0.5) + 1):
        if N % i != 0:
            continue
        else:
            j = N // i
            min_ = min(min_, i + j - 2)
    print(min_)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

n_sqrt = int(math.sqrt(n))
for i in range(n_sqrt, 0, -1):
    if n % i == 0:
        print(i + 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(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N=int(input())
arr=make_divisors(N)

#print(arr)
n=N**(0.5)

min_s=10**10
min_a=-1
for i,a in enumerate(arr):
  if min_s>abs(a-n):
    min_a=a
    min_s=abs(a-n)
print(min_a+N//min_a-2)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



def main():
  N = int(input())
  ret = N-1
  for i in range(1,int(N**0.5)+1):
    if N%i != 0:
      continue
    else:
      ret = min(ret,i+N//i-2)
  return ret

print(main())

Submission status: Accepted

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

print(min(ans))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

divs = []

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

ans = 1000000000007

for i, j in divs:
    ans = min(ans, i-1+j-1)

print(ans)

Submission status: Accepted

Solution code:
n=int(input());l=1
for i in range(2,int(n**.5)+1):
 if n%i<1:l=i
print(l+n//l-2)

Submission status: Accepted

Solution code:
def divisor(n):
    ass = float('inf')
    for i in range(1,int(n**0.5)+1):
        tmp = 0
        if n%i == 0:
            tmp += i
            tmp += n//i
            ass = min(ass, tmp)
    return ass

def main():
    N = int(input())
    tmp = divisor(N)
    print(tmp-2)

  

if __name__ == "__main__":
    main()

Submission status: Accepted

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

N = int(input())

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

l = divisor(N)

s = 0
t = len(l)-1
while s < t:
    s += 1
    t -= 1

print(l[s]+l[t]-2)

Submission status: Accepted

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


if __name__ == '__main__': main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()

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

Submission status: Accepted

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

Submission status: Accepted

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

class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

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

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed + 1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes

prime = Prime()
if prime.is_prime(n):
    print(n - 1)
else:
    for i in range(math.ceil(math.sqrt(n)),0,-1):
        if n % i == 0:
            break
    print(i + n // i - 2)

Submission status: Accepted

Solution code:
import math
n = int(input())
for i in range(1,int(math.sqrt(n))+1):
    if n%i == 0:
        a = i
        b = n//i
print(a+b-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())

vD = make_divisors(N)
#print(vD)

res = min(d + N//d - 2 for d in vD)
print(res)

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors =  float('inf')
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors = min(divisors,i + n//i -2)
    # divisors.sort()
    return divisors


n = int(input())

distance = make_divisors(n)
print(distance)

Submission status: Accepted

Solution code:
import math

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

print(a+b-2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from math import sqrt

def get_yakusu(n):
    i = 1
    ans = []
    while i**2 <= n:
        if n % i == 0:
            ans.append((i, n//i))
        i += 1
    return ans

def main():
    n = int(input().strip())
    y = get_yakusu(n)
    ans = 10 ** 20
    for a, b in y:
        ans = min(ans, a-1+b-1)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve(N: int):
    x = 1
    for i in range(1, math.ceil(math.sqrt(N))+1):
        m = N // i
        d = N % i
        if d == 0:
            x = max(1, i)
    print(x+N//x-2)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

border = int(N**0.5)
for x in reversed(range(1,border+1)):
    if N % x == 0:
        goal = [x, N//x]
        break

print(sum(goal)-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())
div = make_divisors(N)

minimum=N*2
for elem in div:
    A=elem
    B=N//elem
    if(A+B)<minimum:
        minimum=A+B
print(minimum-2)

Submission status: Accepted

Solution code:
import math

def divisor(num):
    if num < 0:
        return 0
    if num == 1:
        return [1, ]

    divisor_list = [1, ]
    divisor_list_r = [num, ]

    i = 2
    while i * i <= num:
        if num % i == 0:
            divisor_list.append(i)
            # divisor_list_r.append(num//i)
        i += 1
    return divisor_list
    #return divisor_list+divisor_list_r[::-1]


N = int(input())
div_list = divisor(N)
ans = div_list[-1] + N // div_list[-1] - 2
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

print(out)

Submission status: Accepted

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

import math


def solve(n):
    dmax = 0
    for d in range(1, int(math.sqrt(n)) + 1):
        if n % d == 0:
            dmax = max(dmax, d)
    cmax = n // dmax
    res = (cmax - 1) + (dmax - 1)
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())

B=N
for i in range(1,N+1):
    j=N//i
    if i>j:
        break
    if N%i==0:
        B=j
print(int((B-1+N/B-1)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
min_c = n - 1

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

Submission status: Accepted

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

Submission status: Accepted

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


def main():
    import math
    import collections
    import itertools

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



if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def make_divisors(n):
    """自然数nの約数を列挙したリストを出力する
    計算量: O(sqrt(N))
    入出力例: 12 -> [1, 2, 3, 4, 6, 12]
    """
    divisors = []
    for k in range(1, int(n**0.5) + 1):
        if n % k == 0:
            divisors.append(k)
            if k != n // k:
                divisors.append(n // k)
    divisors = sorted(divisors)
    return divisors


n = int(input())
ans = make_divisors(n)
res = 10**18
for i in range(len(ans)):
    tmp = ans[i] + n // ans[i] - 2
    res = min(tmp, res)
print(res)

Submission status: Accepted

Solution code:
N = int(input())

c = 1
ans = 10**18
while c <= N**0.5:
    if N%c == 0:
        ans = min(ans, c+N//c)
    c += 1
    
print(ans-2)

Submission status: Accepted

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

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


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

Submission status: Accepted

Solution code:
N = int(input())
rs = []
for n in range(1, N+1):
  if n*n > N:
    break
  if N%n == 0:
    r = n+N//n-2
    rs.append(r)
r = min(rs)
print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
k = 1
while True :
    if k * k > N :
        break
    else:
        k += 1
for i in range(k,0,-1):
    if N % i == 0 :
        a = i
        b = N // i
        print(a + b -2)
        exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

N = INT()

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