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())
ans = 1
i=1
while i*i<=n:
    if n%i==0:
        ans = i
    i+=1

ans += n//ans
ans -= 2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

print(shortest - 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, n // i))
            if i != n // i:
                divisors.append((n // i, i))

    divisors.sort()
    return divisors


div = make_divisors(int(input()))
ans = 10**12
for a, b in div:
    ans = min(ans, a + b - 2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
minimum = 10**100
def prime_divisors(X):
    L=[]
    for i in range(2,math.floor(X**0.5)+1):
        if X % i == 0:
            L.append(i)
    return L
N = int(input())
L = prime_divisors(N)
L.append(1)
for prime in L:
    if (prime + N//prime - 2) < minimum:
        minimum = (prime + N//prime - 2)
print(minimum)

Submission status: Accepted

Solution code:
N = int(input())
from math import sqrt
def get_divs(n):
  divs = []
  for i in range(1, int(sqrt(N)) + 1):
    if n % i == 0:
      divs.append((i, n // i))
  return divs
ans = float('inf')
divs = get_divs(N)
for x, y in divs:
  ans = min(ans, x + y - 2)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math

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

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

nums = divisor(n)
total = []
for i in range(len(nums)):
    s = int(n/nums[i])
    total.append(s-1 + nums[i]-1)

print(min(total))

Submission status: Accepted

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

Submission status: Accepted

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

while mid >=1:
    if n % mid == 0:
        print(mid + n//mid -2)
        break
    mid -= 1

Submission status: Accepted

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

n = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())

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

print(now_answer)

Submission status: Accepted

Solution code:
from itertools import takewhile

N = int(input())
print(min(i+N//i-2 for i in 
          takewhile(lambda i: i*i<=N, range(1, N))
          if N%i==0))

Submission status: Accepted

Solution code:
import math

n = int(input())

ans = []

def n2divide(n):
    for i in range(1, int(math.sqrt(n))+1):
            if n % i == 0:
                ans.append(i + n/i -2)   
    return ans
    
    
a = n2divide(n)
print(int(min(a)))

Submission status: Accepted

Solution code:
import math

n = int(input())

array = []
ans = []

def n2divide(n):
    for i in range(1, int(math.sqrt(n))+1):
            if n % i == 0:
                array.append(i)
                
    for j in array:
        ans.append(j + n/j -2)
        
    return ans
    
    
a = n2divide(n)
print(int(min(a)))

Submission status: Accepted

Solution code:
import math

def main():
    N = int(input())
    rN = math.ceil(math.sqrt(N))
    minDist = float('inf')
    for a in range(1, rN+1):
        if N % a == 0:
            minDist = min(minDist, a+N/a-2)
    print(int(minDist))


main()

Submission status: Accepted

Solution code:
N = int(input())

min_combi = (1, N)

for n in range(2, int(N**0.5)+1):
    if N % n == 0:
        combi = (n, int(N/n))
        if sum(min_combi)-2 > sum(combi)-2:
            min_combi = combi

print(sum(min_combi)-2)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math

def propare():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))

    solve(N)

def solve(N: int):
    # Symmetry, a<=b, a<=math.sqrt(N)
    N_max = min(N, 1000000000000)
    a_max = int(math.sqrt(N_max))
    tmp_list = []
    for a in range(1, a_max+1):
        if N%a == 0:
            b = int(N/a)
            tmp_list.append((a, b))

    if tmp_list:
        answer = tmp_list[0][0] + tmp_list[0][1]

    for i_tp in tmp_list:
        tmp = i_tp[0] + i_tp[1]

        if tmp < answer:
            answer = tmp

    print(answer - 2)
    return

 
if __name__ == "__main__":
    propare()

Submission status: Accepted

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

min_count = 1000000000000
pre_i = 0
pre_j = 0

for i in range(1, int(math.sqrt(n))+1):
  j = n / i
  f, s = math.modf(j)
  if pre_i == j and pre_j == i:
    break
  if str(f) == "0.0":
    count = (i - 1) + (j - 1)
    if count <= min_count:
      min_count = count
    pre_i = i
    pre_j = j

print("{:.0f}".format(min_count))

Submission status: Accepted

Solution code:
import math

N = int(input())

x = 0
y = 0

ans = 10**12 + 1

for n in range(1, math.floor(math.sqrt(N)) + 1):  
  if N % n == 0:
    x = n
    y = math.floor(N / x)

    t = ((x - 1) + (y - 1))

    if ans > t:
      ans = t

print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())
ans = 1000000000000000000 

for i in range(1, N):
  if i * i > N : break
  if N % i != 0: continue

  j = N / i
  ans = min(ans, i + j - 2)

print(int(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache
import heapq

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

MOD = int(1e09) + 7

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
from math import sqrt
def get_divs(n):
  divs = []
  for i in range(1, int(sqrt(n)) + 1):
    if n % i == 0:
      divs.append((i, n // i))
  return divs

divs = get_divs(N)
ans = float('inf')
for x, y in divs:
  ans = min(ans, (x + y - 2))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]
N = int(input())
flag = 0

for i in range(math.floor(math.sqrt(N))):
  if(N%(math.floor(math.sqrt(N))-i)==0):
    a = int(N/(math.floor(math.sqrt(N))-i))
    b = math.floor(math.sqrt(N))-i
    break

ans = a+b-2
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from numpy import linalg as LA

N = int(input())
li = [[1,N]]

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

ans = 10**12
for i in li:
    x,y = i
    tmp = LA.norm([x-1,y-1],1)
    if ans > tmp:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
li = [[1,N]]

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

ans = 10**12
for i in li:
    x,y = i
    tmp = x-1+y-1
    if ans > tmp:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
# 2020/01/23
# AtCoder Beginner Contest 144 - C

# Input
n = int(input())

nsq = int(n ** (1/2)) + 1

x = nsq
y = nsq

while x >= 1:
    if n % x == 0:
        ans = (x - 1) + int( (n / x) - 1)
        break
    else:
        x = x - 1

# Output
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

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

sqrt = int(math.sqrt(N))

for i in range(sqrt, 0, -1):
  if ( (N / i) % 1 ) == 0:
    tenx = i
    teny = int(N/i)
    break

print(tenx + teny - 2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
bar=10**12
d=[]
for i in range(1,int(N**0.5)+1):
  if N%i==0 and i+N//i<bar:
    d.append(i+N//i)
    bar=i+N//i
#print(d)
print(min(d)-2)

Submission status: Accepted

Solution code:
import math

N = int(input())

result1 = 0
result2 = 0
ans = float("inf")
for count in range(1,int(math.sqrt(N))+1):
    if N % count == 0:
        ans = min(ans,count + N // count -2)


print(ans)

Submission status: Accepted

Solution code:
N = int(input())
sqrtN = N**(1/2)

minval = N

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

print(minval)

Submission status: Accepted

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


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

    divisors.sort()
    return divisors


div = make_divisors(N)
print(min(div))

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:

import sys
import heapq
import math

INF = float("inf")


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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())

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

print(min([x[0] + x[1] for x in divisor]) - 2)

Submission status: Accepted

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

    count = n + 1

    for i in range(1,int(n**0.5)+1):
        if n % i == 0 and n // i + i < count:
            count = n // i + i

    print(count-2)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
curMin = 10**12+1
for i in range(1, int(N**0.5)+1):
    if N % i == 0:
        chk = (i - 1) + (N//i - 1)
        if curMin <= chk:
            break
        else:
            curMin = min(curMin, (i - 1) + (N//i - 1))
print(curMin)

Submission status: Accepted

Solution code:
def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    x = 3
    while x * x <= n:
        if n % x == 0:
            return False
        x += 2
    return True


def get_n(N):
    import math

    n = 0
    for i in range(2, 1 + math.ceil(math.sqrt(N))):
        if N % i == 0:
            n = i
    return n


N = int(input())
if is_prime(N):
    print(N - 1)
else:
    n = get_n(N)
    print(n + N // n - 2)

Submission status: Accepted

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

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

print(temp - 2)

Submission status: Accepted

Solution code:
import math

N = int(input())
root_N = int(math.sqrt(N))
FLAG = False

for i in range(2, root_N + 1):
    rev = root_N - i + 2

    if (N%rev == 0):
        FLAG = True
        break

if (FLAG):
    answer = int(N/rev) + rev - 2
else:
    answer = N - 1

print(answer)

Submission status: Accepted

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

ans = float("inf")
for i in range(1, int(math.sqrt(n))+1):
    if n%i == 0:
        ans = min(ans, i-1+(n//i)-1)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
B = int(pow(N, 0.5) + 1)

tmp = pow(10, 12)
for b in range(1, B):
    if N % b == 0:
        a = N // b
        if tmp > a + b - 2:
            tmp = a + b - 2

print(tmp)

Submission status: Accepted

Solution code:
import itertools
import functools
import operator

N = int(input())

# nの約数をすべて求める
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

# 総積
prod = functools.partial(functools.reduce, operator.mul)

dists = []
# N = i*jとなる(i,j)のすべての組
for i in make_divisors(N):
    j = int(N/i)
    # print(i,j)

    # (i,j)までの距離
    dists.append(i-1 + j-1)

print(min(dists))

Submission status: Accepted

Solution code:
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
snm = lambda: map(str, input().split())
nl = lambda: list(map(int, input().split()))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

ans = N
for i in range(1, int(N**0.5) + 1):
    j, m = divmod(N, i)
    if m != 0:
        continue
    ans = min(ans, i + j - 2)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
A=int(input())

K = int(A**0.5)
for i in range(K):
    j = K-i
    if A%j==0:
        break
print(j+A//j-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

def square(n):

  right = n
  left = 0

  while(right - left > 1):

    middle = (right + left) // 2

    if (middle ** 2) < n:
      left = middle 
    if (middle ** 2) > n:
      right = middle 
    if (middle ** 2) == n:
      break

  if middle**2 == n:
    return(middle)

  if middle**2 != n:
    return(left)

i = 0
j = 0
res = 0

for k in range(1, square(n) + 1):
  if n % k == 0:
    i = k
    j = n // k

res = i + j - 2
print(res)

Submission status: Accepted

Solution code:
N = int(input())

divs = set()
for i in range(1, int(N**0.5)+1):
    if N % i == 0:
        q = N // i
        divs.add((min(q, i), max(q, i)))

res = float("inf")
for a, b in divs:
    res = min(res, a+b-2)

print(res)

Submission status: Accepted

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

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)
gojyu=[]
for j in divisors:
    kyori = j + n/j - 2
    gojyu.append(int(kyori))
print(min(gojyu))

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

ans = 10 ** 15
div_list = make_divisors(n)
for temp in div_list:
    temp2 = n//temp
    ans = min( temp + temp2 - 2 ,ans    )
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import math
 
def main():
    N = int(input())
 
    for a in reversed(range(1, int(math.sqrt(N))+1)):
        if N % a == 0:
            print(int(a + N/a - 2))
            sys.exit()
 
main()

Submission status: Accepted

Solution code:
import sys


def solve(inp):
    N = int(inp.readline().strip())

    r = 1001001001001
    for i in range(1, min(1000000, N) + 1):
        if N % i != 0:
            continue
        r = min(r, i + int(N / i) - 2)

    return str(r)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    a = 0
    b = 0

    M = int(N**(1/2))
    for i in range(1, M+1):
        if N%i == 0:
            a = i
            b = (N//i)
    print(a + b - 2)
    return 0
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a,b=0,n
for i in range(1,int(n**0.5)+1):
  j=n//i
  if j-i<b-a and i*j==n:
    a,b=i,j
a= a-1 if a>=1 else 0
b= b-1 if b>=1 else 0
print(a+b)

Submission status: Accepted

Solution code:
import math

n = int(input())

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

Submission status: Accepted

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

N = int(input())
dev_max = divisors(N)[0]

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N = int(input())
root_N = int(math.sqrt(N)) + 1
A = 100000000000000000000000000000000000

for i in range(1, root_N):
    if N % i == 0:
        B = N//i
        A = min(A, B)

ans_1 = A
ans_2 = N//A
ans = ((ans_1)-1) + ((ans_2)-1)

print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())

s = set()
c = 0
x = 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
sum = N+1

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

print(sum)

Submission status: Accepted

Solution code:
from math import sqrt, ceil


def main():
    N = int(input())
    lst = []
    for a in range(1, ceil(sqrt(N)) + 1)[::-1]:
        if N % a == 0:
            b = N // a
            lst.append(a + b - 2)

    print(min(lst))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

ret = float('inf')
i = 1

while i * i <= N:
    if N % i != 0:
        i += 1
        continue
    ret = min(ret, i + N // i - 2)
    i += 1

print(ret)

Submission status: Accepted

Solution code:
from math import sqrt, floor

N = int(input())

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

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n = int(input())

for i in reversed(range(int(math.sqrt(n))+1)):
  if n%i == 0:
    print(int(i+(n/i)-2))
    exit()

Submission status: Accepted

Solution code:
import numpy as np
import math
import itertools

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())
yakusu = make_divisors(N)
min_tasi = 10**15

for i in range(len(yakusu)):
  other = N / yakusu[i]
  tasi = yakusu[i] + other
  
  if tasi < min_tasi:
    min_tasi = tasi

print(int(min_tasi) - 2)

Submission status: Accepted

Solution code:
import math

n = int(input())

mx = math.ceil(n ** 0.5)

for i in reversed(range(1, mx + 1)):
    if n % i == 0:
        print(int(i + n / 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

div = make_divisors(N)
if len(div) % 2 == 0:
	ind_2 = len(div) // 2
	ind_1 = ind_2 - 1
	print(div[ind_1] + div[ind_2] -2)
else:
	ind = len(div) // 2
	print(div[ind] * 2 -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)
            divisors.append(n//i)

    divisors.sort()
    return divisors

ans=make_divisors(n)
print(ans[len(ans)//2-1]+ans[len(ans)//2]-2)

Submission status: Accepted

Solution code:
from math import sqrt

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
m = int(np.sqrt(N))
while N % m != 0:
    m += -1
print(m + N//m - 2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))


N = int(input())
ans = 10 ** 12
for i in range(1, math.ceil(N**0.5)+1):
    if N / i == N // i:
        # print(i, N // i)
        ans = min(ans, i + N // i - 2)
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

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

# main()
print(main())

Submission status: Accepted

Solution code:
# a-bが最小となる、a*b=nを満たすa,b(a>=b)を見つける作業。
# 素因数分解してすべての組み合わせで2数を作って...と考えたけどあきらかにダルい
# ダルいので全探索。1から順に割って、割り切れた数をbとする
# 10^12とデカイが、a*b=n(a>=b)と考えた時、a*a>=nだし、せいぜいaは平方根までの探索でいい
n = int(input())
ans = 10 ** 13

for v in range(1, int(n ** 0.5) + 1):
    a = v
    if n % a != 0:
        continue
    b = n // a
    ans = min(ans, a - 1 + b - 1)

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    s = int(n ** 0.5) + 1
    for i in range(s,0,-1):
        if n % i == 0:
            return i + n//i - 2

    return n - 1


print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

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

n = math.sqrt(N)
if n.is_integer():
  x = round(n) - 1
  print(2 * x)
else:
  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)
  if len(l) % 2 == 0:
    x = l[len(l) // 2 - 1]
    y = l[len(l) // 2]
    print(x + y - 2)

Submission status: Accepted

Solution code:
N = int(input())
X=10**12
Y=10**12
flag = 0
for i in range(2,int(N**0.5)+2):
  if N%i==0:
    flag = 1
    temp = N//i
    if X+Y > temp+i:
      X = i
      Y = temp
      
if flag==0 or X+Y > N+1:
  X = N
  Y = 1
print(X+Y-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n = int(input())
# 約数の合計が最低の約数のペアを求める
def make_div(n):
    divi = []
    for i in reversed(range(1,int(math.sqrt(n))+1)):
        if n%i == 0:
            return [i, n//i] 

print(sum(make_div(n))-2)