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 = n - 1
for i in range(2, 10**6+1):
  
  if n%i==0 and i+n/i-2<ans:
    ans = int(i + n / i - 2)
print(ans)

Submission status: Accepted

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

    return divisors

n = int(input())

li = make_divisors(n)

ans = 10 ** 10

for i in li:
    j = n // i
    ans = min(ans,i + j)

print(i + j - 2)

Submission status: Accepted

Solution code:
import math

a = int(input())
flag = False
result = 1e13
for i in range(2, int(math.sqrt(a)) + 1):
    if a % i == 0:
        flag = True
        result = min(result, i + int(a / i) - 2)
if not flag:
    print(a - 1)
else:
    print(result)

Submission status: Accepted

Solution code:
N = int(input())
ans=1e+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
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
# from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def divisor_pairs(n):
    res = set()
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            a,b = i,n//i
            res.add((a,b))
    res = list(res)
    res.sort()
    return res

def main():
    """ main """
    N = int(input())
    pairs = divisor_pairs(N)
    ans = float('inf')
    for x,y in pairs:
        ans = min(ans,abs(x-1)+abs(y-1))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
input  = sys.stdin.readline
 
N = int(input())
chk = math.floor(math.sqrt(N))
for i in range(chk, 0, -1):
  a = i
  if N%a != 0:
    continue
  b = N/a
  print(int(a+b-2))
  break

Submission status: Accepted

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

    # divisors.sort()
    return divisors
n=int(input())

d=make_divisors(n)


count=0
ans=[]
for i in d:
    pair=n//i
    count=(pair-1)+(i-1)
    ans.append(count)

print(min(ans))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    return


# B
def B():
    return


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


# D
def D():
    return


# E
def E():
    return


# F
def F():
    return


# Unittest
def resolve():
    C()
    return


# Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
import math
data = 1000000000000
N = int(input())
for i in range(1,int(math.sqrt(N))+1):
    j = N/i
    if j-int(j) == 0:
        if data >i+int(j)-2:
            data = i+int(j)-2

print(data)

Submission status: Accepted

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

Submission status: Accepted

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

pairs = [[i, N //i] for i in range(1, root+1) if N % i == 0]

move = min([pair[0] + pair[1] -2 for pair in pairs])
print(move)

Submission status: Accepted

Solution code:
# coding: utf-8

a = int(input())
sum = []
result = 0

ub = int(pow(a, 0.5)) + 1

for i in range(2, ub):  
  (d, mod) = divmod(a, i)
  if mod == 0:
    sum.append(i + d)

if len(sum) == 0:
  print(a - 1)
else:
  sum.sort()
  print(sum[0] - 2)

Submission status: Accepted

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

for i in range(1, n):
    if i*i > n:
        break
    if n%i == 0:
        fct1, fct2 = i, n//i
        ans = min(ans, abs(i-1) + abs(1 - n//i))

print(ans)

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)
print (min(L)-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
input_number = int(input())
walk_count = int(1000000000000)
number_list_A = range(1,1000001)
#number_list_B = number_list_A

for a in number_list_A:
	if input_number % a == 0:
		b = input_number / a
		new_walk_count = int(a + b - 2)
	if new_walk_count < walk_count:
		walk_count = new_walk_count
	new_walk_count = 1000000000000

print(walk_count)

Submission status: Accepted

Solution code:
n = int(input())

class Kake:
    def __init__(self, n):
        self.n = n

    def div(self):
        div_dict = {}
        
        for i in range(1, int(self.n**0.5)+1):
            if self.n % i == 0 and i <= (self.n/i):
                div_dict[i] = int(self.n / i)     
    
        sa_list = list()
        for i in div_dict:
            sa_list.append((i-1)+(div_dict[i]-1))
        print(min(sa_list))
         
kake = Kake(n)
kake.div()

Submission status: Accepted

Solution code:
N=int(input())

# print(N)
# print(int(N**0.5))
# print('')
a=0
b=0
c=N+1


for i in range(1,int(N**0.5)+1):
    if N%i==0:
        a=i
        b=N/i
        # print(a)
        # print(b)
        c=min([c, a+b])
        # print(c)
        # print('')

c=int(c-2)
print(c)

Submission status: Accepted

Solution code:
N = int(input())
A = []
n = N ** 0.5
p = int(n)

for i in range(1, p + 1):
	if N % i == 0 and i <= n:
		A.append(i)
		
a = int(max(A))
b = int(N / a)
print(a + b - 2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import sqrt, ceil
n = int(input())

distance = 10**13
for i in range(1, ceil(sqrt(n)) + 1):
    if n % i == 0:
        new_distance = n//i + i
        if new_distance < distance:
            distance = new_distance

print(distance - 2)

Submission status: Accepted

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

import math

# 整数の入力
N = int(input())

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

Submission status: Accepted

Solution code:
import math
res = 10**12
n = int(input())
for i in range(1, int(math.sqrt(n)) + 1):
  q, mod = divmod(n, i)
  if(mod == 0):
    res = min([res, (i-1) + (q-1)])
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


def get_input():
    return int(input())


def main():
    N = get_input()

    sqrt_n = int(math.sqrt(N))
    minimum = N + 1
    for p in range(1, sqrt_n + 1):
        if N % p == 0:
            q = N / p
            if p + q < minimum:
                minimum = int(p + q)

    print(minimum - 2)


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def print_ans(input_line):
    """Test Case
    >>> print_ans("10")
    5
    >>> print_ans("50")
    13
    >>> print_ans("10000000019")
    10000000018
    """
    N = int(input_line)
    min_ans = N - 1
    for i in range(1,int(N ** 0.5) + 1):
        q, mod= divmod(N,i)
        if mod == 0:
            min_ans = min(min_ans, q + i -2 )
    print(min_ans)

if __name__ == '__main__':
    print_ans(input())

Submission status: Accepted

Solution code:
n = int(input())

s = int(n**0.5)
temp = n
li = [1]

for i in range(s+1,0,-1):
    if temp%i == 0:
        li.append(i)
        break

t = n//li[-1]

print((t-1) + (li[-1]-1))

Submission status: Accepted

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

def ij(x):
    for i in range(x, 0, -1):
        if n/i == n//i:
            return i, n//i

print(sum(ij(int(sqrt(n)))) - 2)

Submission status: Accepted

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

def ij(x):
    for i in range(x):
        i = x - i
        if n / i == n//i:
            return i, n//i

print(sum(ij(int(sqrt(n)))) - 2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Nov  6 21:49:38 2019

@author: over-
"""

N=int(input())

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

Submission status: Accepted

Solution code:
tall = int(input())
bit = int(tall**(1/2))
while ((tall/bit)%1 != 0):
  bit -= 1
print(int(bit+tall/bit-2))

Submission status: Accepted

Solution code:
data=int(input())
sum=10**12
 
for i in range(10**6):
  a=i+1
  if data%a==0:
    b=data//a
    if a+b<sum:
      sum=a+b
      
print(sum-2)

Submission status: Accepted

Solution code:
n = int(input())

min_step = 10**12

i = 1
j = 1
l = int(n**0.5)+1

for p in range(1, l+1):
    if n % p == 0:
        if i == (n / p) and j == p:
            break
        step = (p + n / p) - 2
        if min_step > step:
            min_step = step
            i = p
            j = (n / p)

print(int(min_step))

Submission status: Accepted

Solution code:
a = int(input())
b = 0
l = int(a**0.5)+1
count = 0
for i in range(l):
    i = i+1
    if a%i == 0:
        j = a//i
    if i*j == a:
        if count == 0:
            count += 1
            c = i
            d = j
        if count>0:
            if (c+d)>(i+j):
                c = i
                d = j
ans = c+d-2
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
goal=[]
step=[]
i=1
while i*i<=N:
     if N%i==0:
          j=N/i
          goal.append([i,j])
     i+=1
n=len(goal)
for i in range(n):
     step.append(goal[i][0]-1+goal[i][1]-1)
print(int(min((step))))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
k=int(n**(1/2))

for i in range(k):
    l=k-i
    if n%l==0:
        print(l+int(n/l)-2)
        break

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#整数nを入力
n = int(input())

x = 1
y = n
#整数nの約数で、平方根以下の最も大きい約数を求める
for i in reversed(range(1, int(n**0.5)+1)):
    if n % i == 0:
        x = i
        y = n / i
        break

#約数＋約数 - 2で答えを求める
print(int(x+y) - 2)

Submission status: Accepted

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


num = int(input())
print(solve(num))

Submission status: Accepted

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

for x in range(1, int(n ** 0.5) + 1):
    if n % x == 0 :
        sum_list.append(int(x + n / x - 2))

print(min(sum_list))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())

import math

s=int(math.sqrt(n))
#print(s)
for i in range(s):
  if n%(s-i)==0:
    k1=s-i
    break

  else:
    k=0

#print(k1)
k2=int(n/k1)

print(k1+k2-2)

Submission status: Accepted

Solution code:
import math

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

print(min(ans))

Submission status: Accepted

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

ans_sum = []
for i in range(1, round(math.sqrt(n) + 2)):
    if n%i == 0:
        ans_sum.append(i-1 + (n//i) -1)

print(min(ans_sum))

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

n = int(input())

divisors = listDivisors(n)

if len(divisors) % 2 == 1:
    a = divisors[-1]
    b = divisors[-1]
else :
    a = divisors[-1]
    b = divisors[-2]
    
answer = a + b - 2

print(answer)

Submission status: Accepted

Solution code:
n = int(input())
i = 1
ans = n
while i * i <= n:
    j, m = divmod(n, i)
    if m == 0:
        ans = min(ans, i + j - 2)
    i += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
rn = int(n**0.5)+1
flag = True
ans = 0
while flag:
    if n%rn == 0:
        ans = rn + n//rn -2
        flag = False
    rn -= 1
print(ans)

Submission status: Accepted

Solution code:
import math

N=int(input()) 
ans=N-1
for i in range(int(N**0.5), 1, -1):
  a=N//i
  if (a*i==N):
    if (a-1+i-1<ans):
      ans=a-1+i-1

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt, floor

n = int(input())
t = floor(sqrt(n))

while n % t != 0:
    t -= 1

print(t + n // t - 2)

Submission status: Accepted

Solution code:
# 素因数分解
def prime_factorization(N):
    tmp = N
    ans = []
    for i in range(2, int(N ** 0.5) + 1):
        count = 0
        while tmp % i == 0:
            tmp //= i
            count += 1
        if count != 0:
            ans.append([i, count])
    if tmp != 1:
        ans.append([tmp, 1])
    if ans == []:
        ans.append([N, 1])
    return ans

N = int(input())
prime_N = prime_factorization(N)
if len(prime_N) == 1 and prime_N[0][1] == 1:
    print(N - 1)
    exit()
start = int(N ** 0.5) + 1
ans_a = 0
ans_b = 0
for a in range(start, 1, -1):
    b = N // a
    if N == a * b:
        ans_a = a
        ans_b = b
        break

print(ans_a + ans_b - 2)

Submission status: Accepted

Solution code:
# a+b-2
# N = a*b  よってNの約数を求める
import numpy as np

N = int(input())
U = 10**6+100
x = np.arange(1, U, dtype=np.int64)
div = x[N%x==0]
ans = (div + N//div).min() - 2
print(ans)

Submission status: Accepted

Solution code:
# a+b-2
# N = a*b  よってNの約数を求める

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

Submission status: Accepted

Solution code:
import math

n=int(input())
num=math.ceil(math.sqrt(n))

c=n+2
for i in range(1,num+1):
      if n%i==0 and (i+n//i)<c:
            a=i
            b=n//i
            c=a+b

print(a+b-2)

Submission status: Accepted

Solution code:
import math
a = int(input())
b = math.ceil(math.sqrt(a))
ans = 10000000000000000

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

print(ans)

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())
#print(N)

U=10**6+100
div=np.arange(1,U,dtype=np.int64)
#print(div)

div=div[N%div==0]
#print(div)

div=div+N//div-2
print(div.min())

Submission status: Accepted

Solution code:
import math
a = int(input())
result = 0

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

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]
print((div+N//div).min()-2)

Submission status: Accepted

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

Submission status: Accepted

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


def main():
    N = input_line(int)
    border = int(math.sqrt(N))
    for i in range(border, 0, -1):
        if N % i == 0:
            print((i-1) + (N // i - 1))
            break


def input_line(*types):
    if len(types) == 1:
        return types[0](input())
    else:
        return [t(x) for t, x in zip(types, input().split())]


if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import sqrt

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

Submission status: Accepted

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

rN=int(math.sqrt(N))

ans=8101919114514
for i in range(rN):
  i=i+1
  if N%i==0:
    tmp=N/i
    if tmp<ans:
      #print(i,tmp)
      ans=i+tmp-2
print(int(ans))

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(int(i+n/i-2))
    return divisors
ans = float("inf")
for i in make_divisors(int(input())):
    
    ans = min(ans,i)
print(ans)

Submission status: Accepted

Solution code:
import math
n =int(input())
ar = range(1,int(math.sqrt(n))+1)
distance = n
for factor1 in ar:
  if n%factor1 == 0:
    factor2 = int(n/factor1)
    distance = min(distance,factor1+factor2-2)
print(distance)

Submission status: Accepted

Solution code:
import math

N = int(input())

flag = True
s = math.floor(math.sqrt(N))
for i in range(s, 1, -1):
    if N % i == 0:
        ii = N // i
        print(i - 1 + ii - 1)
        flag = False
        break
if flag:
    print(N - 1)

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:
#coding:utf-8
import math

#移動回数はa+b-2。これを満たす座標(a,b)について、a,bの最小値
#探索範囲はsqrt(N)まで、a<=b
n = int(input())
ans = n-1

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

print(ans)

Submission status: Accepted

Solution code:
from math import *

n = int(input())

mn = n

i1 = 0
i2 = n

for i in range(1,ceil(sqrt(n))+1):
    
    if(n%i==0):
        k = n//i
        if(abs(k-i)<mn):
            i1 = i
            i2 = k
            
ans = i1 + i2 -2

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

n=int(input())
a=int(sqrt(n))
d=[]
for i in range(1,a+1):
    if n//i==n/i:
        d.extend([i,n//i])

print(d[-1]+d[-2]-2)

Submission status: Accepted

Solution code:
def p_a():
    A, B = map(int, input().split())
    print(A * B if A < 10 and B < 10 else -1)


def p_b():
    N = int(input())
    for i in range(1, 10):
        for j in range(1, 10):
            if N == i * j:
                print("Yes")
                exit()
    print("No")


import math


def p_c():
    N = int(input())
    m = int(math.sqrt(N))

    for i in reversed(range(1, m + 1)):
        if N % i == 0:
            print(i + N // i - 2)
            break


def p_d():
    pass


def p_e():
    pass


def p_f():
    pass


if __name__ == '__main__':
    p_c()

Submission status: Accepted

Solution code:
N=int(input())    #N<=10**12

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7
n = int(input())

ans = 10**13
for x in range(1, int(math.sqrt(n)) + 1):
    if n % x == 0:
        y = n // x
        ans = min(ans, x + y - 2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

p = 1

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

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

Submission status: Accepted

Solution code:
from math import sqrt, ceil


def square_like_factors(n):
  root_n = ceil(sqrt(n))
  for i in reversed(range(1, 1 + root_n)):
    if n % i == 0:
      return (i, n // i)
  return (1, n)


n = int(input())
a, b = square_like_factors(n)
print(a + b - 2)

Submission status: Accepted

Solution code:
import sys
n=int(input())
L=[]
for i in range(1,int(n**(1/2))+1):
    if n//i == n/i:
        L.append(n//i+i-2)
print(min(L))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C - Walk on Multiplication Table
n = (int)(input())

minimum = 1e18
i = 1
while(i*i <= n):
    if n % i != 0:
        i += 1
        continue;
    j = (int) (n / i)
    minimum = min(i + j - 2, minimum)
    i +=1

print(minimum)

Submission status: Accepted

Solution code:
N = int(input())

q1 = 1
q2 = N

step = q1 + q2 - 2

for i in range(N):
    x = i+1
    if x**2 > N:
        break
    if N % x == 0:
        q1_cand = x
        q2_cand = N / x
        step_cand = q1_cand + q2_cand - 2
        if step_cand < step:
            step = step_cand
print(str(int(step)))

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
N = int(input())
heap = []
heapify(heap)
for i in range(1, int(N**(0.5)) + 1):
    if N % i == 0:
        heappush(heap, i - 1 + N // i - 1)
print(heappop(heap))

Submission status: Accepted

Solution code:
a = int(input())
i = 1
otv = 10**20
while i*i <= a:
    if a%i == 0:
        otv = min(otv, a//i + i - 2) 
    i += 1
print(otv)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools

def sRaw():
    return input().rstrip("\r")

def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    
def ZAlgo(s):
    l = len(s)
    A = [0]*l
    i =1
    j =0
    A[0]=l
    while i<l:
        while i+j<l and s[j] == s[i+j]:
            j+=1
        if j==0:
            i+=1
            continue
        A[i]=j
        k=1
        while (i+k<l) and (k+A[k]<j):
            A[i+k] =A[k]
            k+=1
        i+=k
        j-=k
    return A


def main():
    N = iRaw()
    i = 1
    ans = N
    while i*i <= N:
        if N%i ==0:
            j = N//i
            ans = min(ans,i-1+j-1)
        i+=1
    return ans

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

Submission status: Accepted

Solution code:
import math
ans = 10 ** 15

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

print(ans)

Submission status: Accepted

Solution code:
# 191027 C
# 191027 C
import math
N = int(input())
tmpn = math.ceil(math.sqrt(N))

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

Submission status: Accepted

Solution code:
import math

n = int(input())
m = math.ceil(math.sqrt(n))

for i in range(m,0,-1):
    (j, mod) = divmod(n, i)
    if mod == 0:
        print(i+j-2)
        break

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n = int(input())
ans=n

for i in range(1, int(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())
ans = 10**12
root = int(math.sqrt(N))+1
for i in range(1,root):
    if N % i == 0:
        ans = min(ans,(i-1)+(N//i-1))
print(ans)

Submission status: Accepted

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

    return divisors
a = int(input())
b = make_divisors(a)
c = len(b)/2
d = len(b)-1
if c.is_integer()==False:
  print(b[d]*2-2)
else:
  print(b[d]+b[d-1]-2)

Submission status: Accepted

Solution code:
n = int(input())

pair = [n, 1]
i = 2
d_min = n**2 + 1
while i * i <= n:
    if n % i == 0 and d_min > (n/i)**2 + i**2:
        pair[0] = int(n/i)
        pair[1] = i
    i += 1

print(pair[0]+pair[1]-2)

Submission status: Accepted

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

minimum=n-1
for i in range(2,n2+1):
  if(n%i==0):
    minimum=min(minimum,(n//i-1)+(i-1))

print(int(minimum))

Submission status: Accepted

Solution code:
from math import sqrt, ceil

N = int(input())



n,m = 0,0
for i in reversed(range(1, ceil(sqrt(N))+1 )):
  if N % i == 0:
    n = i
    m = int(N / i)
    break

print(n-1+m-1)

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
a = int(input())
ar = make_divisors(a)
br = []
for r in ar:
    br.append((r - 1) +  ((a // r) - 1))
print(min(br))

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


N = int(sys.stdin.readline())

divs = get_divisors(N)
ans = INF
for d in divs:
    a = N // d
    b = d
    ans = min(ans, a + b)
print(ans - 2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
list=[]
for i in range(1,int(n**0.5+1)):
  if n%i == 0:
    list.append(int(i+n/i))
print(min(list)-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)
    return divisors

divisors_lst = make_divisors(n)

mins = 10**100
for i in divisors_lst:
    j = n // i
    if i + j < mins:
        ans = i + j
        mins = i * j

print(ans-2)

Submission status: Accepted

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