Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

10

Sample Output 1

5

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

Sample Input 2

50

Sample Output 2

13

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

Sample Input 3

10000000019

Sample Output 3

10000000018

Both input and output may be enormous.



Sample input:
10


Sample output:
5

Submission status: Accepted

Solution code:
import math

a=int(input())
x=(math.ceil(a**(1/2)))
for i in range(x+1):
 if a%(x-i+1)==0:
  print(int(x-i-1+(a/(x-i+1))))
  break

Submission status: Accepted

Solution code:
N = int(input())
import math
def is_prime(n):
  if n == 1: return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False
  return True
if is_prime(N):
  print(N-1)
else:
  a = math.floor(math.sqrt(N))
  while True:
    if N%a==0:
      break
    a=a-1
  print(int(a+N/a-2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def make_divisors(n):
  divisors = []
  for i in range(1, int(math.sqrt(n))+1):
    if n % i == 0:
      x = i
      y = n // i
      divisors.append([x, y])

  return divisors

def list_sum(t_list):
  return t_list[0] + t_list[1]

n = int(input())
yakusu = make_divisors(n)

data = list(map(list_sum, yakusu))
print(min(data) - 2)

Submission status: Accepted

Solution code:
import math
n = int(input())
x = range(1,math.ceil(n**0.5)+1,1)
b = []
for a in x:
    if n % a == 0:
        y = n//a
        b.append(y)
b_min = min(b)
a = n // b_min
sum = a+b_min-2
print(sum)

Submission status: Accepted

Solution code:
N=int(input())
M=int(N**0.5)
L=0

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

print(int(L))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n=int(input())
m=math.sqrt(n)
m=math.floor(m)+1
li=[]
for i in range(1,m):
    a=i+n/i
    li.append(a)
li=[li[i] for i in range(m-1) if li[i].is_integer()]
print(int(min(li))-2)

Submission status: Accepted

Solution code:
N=int(input())
n=round(N**(1/2))
for i in range(1,n+2):
	if N/i==N//i:
		ans=i+N/i-2
print(int(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())

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)
    return divisors

ans=make_divisors(N)

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

for i in range(len(ans)):
    if i%2!=0:
        continue
    if temp>ans[i]+ans[i+1]-2:
        temp=ans[i]+ans[i+1]-2
print(temp)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
S = N+1
from math import sqrt
for a in range(int(sqrt(N))+2, 0, -1):
    b, y = divmod(N, a)
    if y != 0:
        continue
    S = min(S, a+b)
print(S-2)

Submission status: Accepted

Solution code:
N=int(input())
import math
A=math.sqrt(N)
B=math.floor(A) 
while True:
    if N % B == 0 :
        print(B+N//B-2)
        break
    else :
        B-=1
        continue

Submission status: Accepted

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

Submission status: Accepted

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


if len(divisors)%2 > 0:
  print (divisors[p] + divisors[p] -2)
else:
  print (divisors[p] + divisors[p -1] -2)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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
list = make_divisors(n)
root = n**0.5
for i in range(len(list)-1):
    if (list[i] <= root and list[i+1] >root):
        a = list[i]
b = n //a
print(a+b-2)

Submission status: Accepted

Solution code:
def make_divisors(n):
    ans = float('inf')
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ans = min(ans, i+N//i-2)
            if i != n // i:
                ans = min(ans, n//i+N//(n//i)-2)

    return ans

N = int(input())
print(make_divisors(N))

Submission status: Accepted

Solution code:
n=int(input())
a = []
for i in range(1, int(n**0.5)+1):
  if n % i == 0:
    a.append(i)
    if i != n // i:
      a.append(n//i)
b = list(map(int,a))
anc =1000000000000
for l in range(len(b)):
  if int(n/b[l]+b[l])-2<anc:
    anc = int(n/b[l]+b[l])-2
print(anc)

Submission status: Accepted

Solution code:
import math
n = int(input())
max_int = int(math.sqrt(n))+1
i = max_int
ans_tmp = n
while i > 0:
    warikire = n%i
    waru = int(n/i)
    if warikire == 0 and waru <= ans_tmp:
        ans_tmp = waru
    i-=1
warukazu = int(n/ans_tmp)
print(warukazu+ans_tmp-2)

Submission status: Accepted

Solution code:
import math

t = int(input())
ans = t - 1

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

flg = is_prime(t)

tmp = math.sqrt(t)
a = math.ceil(tmp)
#print(a)

if flg == True:
    ans = t -1
else:
    for i in range(0 , a + 1):
        if t % (a - i) == 0:
            syou = int(t/(a - i))
            ans = (a - i) + syou - 2
            break

# for i in range(0, a + 1):
#     if a * (a - i) == t:
#         ans = a + (a-i) -2
#         break

print(ans)

Submission status: Accepted

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

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

maxStep = N-1

divs = make_divisors(N)
#print(divs)

for i in range(1,len(divs)+1):
	A=divs[i-1]
	B=divs[-i]
	#print(A,B,A-1 + B-1)
	if  A-1 + B-1 < maxStep:
		maxStep = A-1 + B-1

print(maxStep)

Submission status: Accepted

Solution code:
import math

if __name__ == "__main__":
    N = int(input())
    nsqrt = math.sqrt(N)
    for i in range(int(nsqrt), 0, -1):
        if N % i == 0:
            print(i + N//i - 2)
            exit()

Submission status: Accepted

Solution code:
import math
n = int(input())
sq = math.floor(pow(n, 0.5))
ans = []
for i in range(2, sq + 1):
    if n % i == 0:
        ans.append((i - 1) + ((n // i) - 1))
if len(ans) > 0:
    print(min(ans))
else:
    print(n - 1)

Submission status: Accepted

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

ans = 10**12

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import os

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())
listN = make_divisors(N)
mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(len(listN)):
        x = listN[i]
        y = N//x
        mini = min(x+y,mini)
print(x-1+y-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N = int(input())

M = N
tmp = 0
A = 0

for i in range(2,int(math.sqrt(N))+1):
    if N % i == 0:
        tmp = N / i
        if abs(tmp - i) < M:
            M = abs(tmp-i)
            A = tmp+i
if A == 0:
    print(N-1)
else:
    print(int(A-2))

Submission status: Accepted

Solution code:
import math
n = int(input())
ans = 1 + n

max = math.ceil(n**0.5)

for i in range (2, max+1):
    if n % i == 0 and i + n / i < ans:
        ans = i + n / i

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

n = make_divisors(N)
n.sort()
mannaka_ = int(len(n)/2)
mannaka = mannaka_ - 1
#print(n)
if len(n)%2 == 0:
    print((n[mannaka_]-1)+ (n[mannaka]-1))
else:
    print(n[mannaka_] * 2 - 2)

Submission status: Accepted

Solution code:
N = int(input())
A = 0
ans=0
Oans=5*(10**11)
flag=0

if N%2 == 0:
    A = N//2
else:
    A = (N-1)//2
#print(A)

for i in range(A):
    #print(N/(i+2))
    #print(i+2)
    if N%(i+2) == 0:
        
        ans = i+1 + N/(i+2)-1
        flag = 1
        if Oans < ans:
            ans = Oans
        else:
            Oans = ans
    else:
        if N/(i+2) > i+2:
            continue
        else:
            break
        
if flag == 1:
    print(int(ans))
else:
    print(N-1)

Submission status: Accepted

Solution code:
# https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
pfs = factorization(n)



pf = []
for lis in pfs:
    pf.extend([lis[0] for _ in range(lis[1])])

ab = [1]
for x in pf:
    ab.extend([i * x for i in ab])
    ab = list(set(ab))
    
ans = float("inf")
for y in ab:
    tmp = (n / y) - 1 + y - 1
    ans = min(ans, tmp)
    
print(int(ans))

Submission status: Accepted

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

print(mins)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N=int(input())
c=0
d=10000000000000
rN=int(N**0.5)

for i in range(rN):
    if (N%(i+1)==0) :
        x=i+1
        y=int(N/(i+1))
        if d>(x+y):
            d=x+y

print(d-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())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  b = n // d[i]
  if b == d[i]:
    a.append([d[i], d[i]])
    break
  for j in range(i+1, len(d)):
    if b == d[j]:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)

Submission status: Accepted

Solution code:
import math


def solve():
    N = int(input())
    rN = math.ceil(N ** 0.5)

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/pypy
import sys
N=int(raw_input())

m = pow(N,0.5)


for i in xrange(int(m), -1, -1):
    if N % i == 0:
        print (str((i-1) +(N/i - 1)))
        sys.exit(0)

Submission status: Accepted

Solution code:

import math

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

li = make_divisors(N)

#Nが素数
if len(li) == 1:
    print(N-1)
    exit()
#Nが乗数
n = math.sqrt(N)
str_n = str(n)
if str_n[-1] == '0':
    x = int(n) -1
    y = int(n) -1
    print(x+y)
    exit()


if len(li) % 2 == 0:
    ind = int(len(li) / 2)
else:
    ind = int(len(li) / 2 + 1)

x = li[ind]
y = int(N / x)

x -= 1
y -= 1

print(x+y)

Submission status: Accepted

Solution code:
N = int(input())

i = 1
answer = N - 1
while i * i <= N:
    if N % i == 0:
        new_answer = (i - 1) + ((N / i) - 1)
        if answer > new_answer:
            answer = new_answer
    i += 1

print(int(answer))

Submission status: Accepted

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

    # divisors.sort()
    return (a+b-2)

N = int(input())

print(make_divisors(N))

Submission status: Accepted

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

for i in range(2,int(math.sqrt(N))+1):
    if N%i==0:
        if ((N/i)-1)+(i-1)<dis:
            dis=((N/i)-1)+(i-1)
        else:
            pass
    else:
        pass
print(int(dis))

Submission status: Accepted

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

    # divisors.sort()
    return divisors
N=int(input())
S=[]
l=0
m=0
n=0
a=len(make_divisors(N))
for i in make_divisors(N):
  S.append(i)
S.sort()
l=len(S)
if l%2==0:
  m=S[l//2-1]
  n=N//m
else:
  m=S[l//2]
  n=N//m
print((m-1)+(n-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()
    length = len(divisors)
    if length%2 != 0:
        mov = divisors[length//2] * 2 - 2
    else:
        mov = divisors[length//2 - 1] + divisors[length//2] - 2
    return mov
n = int(input())
k = make_divisors(n)
print(k)

Submission status: Accepted

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

def main():
  x = int(input())
  a = t(x)
  b = x // a
  result = a - 1 + b - 1
  return result
print(main())

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

import math
import bisect
N = int(input())
N_list = sorted(make_divisors(N))
p = bisect.bisect_left(N_list, math.sqrt(N))
n = N_list[p]
print(int(N/n + n - 2))

Submission status: Accepted

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

print(int(res))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

def judge(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 = judge(N)
divisors.sort()
if len(divisors) % 2 == 0:
  while len(divisors) >= 3:
    divisors.pop(0)
    divisors.pop(-1)
  print(max(1, sum(divisors)-2))
else:
  while len(divisors) >= 2:
    divisors.pop(0)
    divisors.pop(-1)
  print(max(1, sum(divisors)*2-2))

Submission status: Accepted

Solution code:
import math

N = int(input())

sq = int(math.sqrt(N))

ans = N

for i in range(1, sq+1):
    if N % i == 0:
        M = i - 1 + int(N / i) - 1
        if ans > M:
            ans = M

print(ans)

Submission status: Accepted

Solution code:
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass
 
 
 
n = int(input())
l = sorted(divisor(n))
if len(l) % 2 == 1:
    print(l[(len(l) // 2)] * 2 - 2)
else:
    print(l[(len(l)//2 - 1)] + l[(len(l)//2)] - 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

min_value = 1000000000000
data = int(input())
ng_flag = False
divisors_array = make_divisors(data)

if len(divisors_array) % 2 == 1:
    divisors_array.append(divisors_array[len(divisors_array)-1])
for i in range(0, len(divisors_array)):
    if(i % 2 == 0):
        first = divisors_array[i] -1 
        second = divisors_array[i+1] -1 
        if first + second < min_value:
            if i == 1:
                min_value = first + second
            else:
                min_value = first + second
print(min_value)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())

mean = int(np.sqrt(n))

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

Submission status: Accepted

Solution code:
import math

def divisor_generator(n):
    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            large_divisors.append(n // i)
    for divisor in reversed(large_divisors):
        yield divisor

n = int(input())


divs = list(divisor_generator(n))
l = len(divs) - 1
best = 2 if n == 1 else min([divs[i] + divs[l-i] for i in range(len(divs)>>1)] )

print(best-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

f=1
x = 0
while f*f <= n:
    if n%f == 0:
        x = f 
    f += 1
y = n//x

print(x + y - 2)

Submission status: Accepted

Solution code:
N=int(input())
l=[]
for i in range(2,int(N**0.5)+1):
    if N % (i) == 0:
       l.append(i)
if len(l) == 0:
    print(N-1)
elif len(l) == 1:
    print(int(N / l[0]) + l[0] -2)
elif len(l) == 2 and N == l[0] * l[1]:
    print(l[0] + l[1] -2)
else:
    distance = 10**12 - 2
    tmp = 0
    for i in range(len(l)):
        for j in range(i, len(l)):
            if N % (l[i] * l [j]) == 0 and distance > (N / (l[i] * l [j])) + (l[i] * l [j]) -2:
              distance = int(N / (l[i] * l [j])) + (l[i] * l [j]) -2
    print(distance)

Submission status: Accepted

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

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:
import math
N=int(input())
tmp=N+1
for i in range(1,int(math.sqrt(N)+1)):
  if N%i==0:
    if i+(N/i)<=tmp:
      tmp=i+(N/i)
if tmp==N+1:
  print(int(N-1))
else:
  print(int(tmp-2))

Submission status: Accepted

Solution code:
#C問題
#考え方：平方根に近いところを探す。
#平方根を切り上げた値からスタート。割り切れた時点で終了。
#TLEになった。原因として考えられるのは何か？ものすごい大きな数の時にうまくいかない？
#素数の時に厳しい。
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
import numpy as np


def getNearestValue(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]

N = int(input())
lis_1 = make_divisors(N)
A = getNearestValue(lis_1,math.sqrt(N))
B = int(N/A)

print(A+B-2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

n = int(input())
res = float('inf')
for a in range(1, int(math.sqrt(n)) + 1):
    if n % a == 0:
        res = min(res, a + n // a - 2)
print(res)

Submission status: Accepted

Solution code:
import math
N = int(input())
n = math.ceil(math.sqrt(N)) + 3

ans = N-1

for i in range(2, n):
    if N % i == 0:
        ans = min(ans, N // i + i - 2)


print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
# n,k = int(input())
# list = list(map(int,input().split()))
# strings = list(map(str, [input() for i in range(amount)]))
import math

n = int(input())
nn = int(math.sqrt(n) // 1)
ans = 0

for i in reversed(range(1,nn+1)):
    # print(i)
    if n % i == 0:
        ans = (i-1)+(n//i-1)
        break

print(ans)

Submission status: Accepted

Solution code:
a = int(input())

dif = a
half = int(a / 2)
for i in range(1,half+1):
	if i <= a / i:
		if a % i == 0:
			div1 = int(i)
			div2 = int(a / i)
			continue
	else:
		break
print(div1 + div2 -2)

Submission status: Accepted

Solution code:
import math
import sys
n = int(input())
sqn = round(math.sqrt(n))
flg = True
if n % sqn == 0:
  print(sqn + n//sqn -2)
  sys.exit()

sqn_add = sqn
sqn_diff = sqn
while flg:
  sqn_add += 1
  sqn_diff -= 1
  if n % sqn_add == 0:
    print(sqn_add + n//sqn_add -2)
    sys.exit()
  elif n % sqn_diff == 0:
    print(sqn_diff + n//sqn_diff -2)
    sys.exit()

Submission status: Accepted

Solution code:
import math
import sys

N = int(input())
for A in range(int(math.sqrt(N)), 0, -1):
    B = N // A
    if A * B == N:
        print(A + B - 2)
        sys.exit()

Submission status: Accepted

Solution code:
import collections
A= int(input())

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

    # divisors.sort()
    return divisors
  
primelist=make_divisors(A)
S = primelist[-1]
G = int(A/S)

print((G-1)+(S-1))

Submission status: Accepted

Solution code:
import math
def fact(n):
  i = 1
  l=[]
  while i <= math.sqrt(n):
    if (n % i == 0) : 
      if (n / i == i) : 
        l.append(i) 
      else : 
        l.append(i)
        l.append(n//i)
    i = i + 1
  return l

n=int(input())
l=fact(n)
xx=0
mini=10000000000000
l.sort()
i,j=0,len(l)-1
while i<j:
  i+=1
  j-=1
# print(l[i],l[j])
print(l[i]+l[j]-2)
# print(xx)


'''
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
3 6 9 12 15 18 21 24 27 30
4 8 12 16 20 24 28 32 36 40
5 10 15 20 25 30 35 40 45 50
'''

Submission status: Accepted

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

for p in reversed(range(1, s + 1)):
#     print(p)
    if N % p == 0:
        p, q = p, N // p
        print(p + q - 2)
        break

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
a = int(input())
b = round(math.sqrt(a))
while a % b != 0:
    b -= 1
c = int(a / b)
print(b + c - 2)

Submission status: Accepted

Solution code:
read = input 
rn = lambda :list(map(int, read().split()))
def reverse_range(r):return range(r-1, -1, -1)
import math

def sol(a):
    best = a + 1
    N = math.sqrt(a)
    N = int(N)
    for i in range(1, N+1):
        if a % i == 0:
            j = a // i
            best = min(best, i+j)
    
    return best
    
a = rn()[0]
print(sol(a)-2)

Submission status: Accepted

Solution code:
N = int(input())

c = 10**100

for a in range(2, int(N**0.5)+1):
    if N % a == 0:
        b = N / a
        if (a-1)+(b-1) < c:
            c = (a-1)+(b-1)
        
print(min((N-1), int(c)))

Submission status: Accepted

Solution code:
import math

def FindAllDivisors(x):
    divList = []
    y = 1
    while y <= math.sqrt(x):
        if x % y == 0:
            divList.append(y)
            divList.append(int(x / y))
        y += 1
    return divList

n = int(input())
a = FindAllDivisors(n)

b = 10000000000
for i in range(len(a)):
  if i%2==1:
    continue
  else:
    bb = a[i]+a[i+1]
    if b >= bb:
      b = bb

print(bb-2)

Submission status: Accepted

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

L = make_divisors(n)
P = []
if math.sqrt(n) % 1 != 0:
    P.append(L[-1])
    P.append(L[-2])
else:
    P.append(L[-1])
    P.append(L[-1])

print(sum(P)-2)

Submission status: Accepted

Solution code:
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

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

if is_prime(n) == True:
    print(n-1)
else:
    ls = (make_divisors(n))
    if (n / ls[-1]) == ls[-1]:
        print(ls[-1]+ls[-1]-2)
    else:
        print(ls[-1]+ls[-2]-2)

Submission status: Accepted

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

    #divisors.sort()
    score_sorted = sorted(divisors.items(), key=lambda x:x[0])
    return score_sorted

N = int(input())
num_dict = make_divisors(N)
print(num_dict[0][0]-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())

tmp = make_divisors(N)
if(len(tmp)%2==0):
    print((tmp[-1]-1)+(tmp[-2]-1))
else:
    print((tmp[-1]-1)+(tmp[-1]-1))

Submission status: Accepted

Solution code:
import math

N = int(input())

def main():
    curr = math.ceil(math.sqrt(N))
    while True:
        m, r = divmod(N, curr)
        if r == 0:
            ans = [m, N // m]
            break
        curr -= 1
    print(sum(ans) - 2)

if __name__ == '__main__':
    main()

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)

    return divisors
l=make_divisors(n)

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

Submission status: Accepted

Solution code:
N = int(input())
ans = N-1
for i in range(int(N ** 0.5), 1, -1):
    x, y = divmod(N, i)
    if y == 0:
        print(i+x-2)
        exit()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

ans = []
for i in range(2,n+1):
  if n %i == 0:
    ans.append(i)
  if i *i > n:
    break

if len(ans) == 0:
  print(n -1)
else:
  print(ans[-1] + int(n / ans[-1]) -2)

Submission status: Accepted

Solution code:
def search(a):
	for i in range(int(a**0.5)+1, 0, -1):
		if a % i == 0:
			return i

a = int(input())
b = search(a)
c = int(a / b)
print(b+c-2)

Submission status: Accepted

Solution code:
import math

N = int(input())

for i in reversed(range(1,math.ceil(math.sqrt(N)+1))):
    if N % i == 0:
        a = i
        b = N / i
        break

print(int(a + b - 2))

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
m=int(np.ceil(np.sqrt(n)))+1
l=[]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
Alist = []

for i in range(1,10**6+1):
    if N%i==0:
        Alist.append(int(i)+int(N//i)-2)
print(min(Alist))