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

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(i + n//i - 2, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

n=int(input())

c=[]

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

if len(c)==0:
    print(n-1)
    sys.exit()
    
print(min(c))

Submission status: Accepted

Solution code:
# coding: utf-8
from math import sqrt

def main():
    N = int(input())
    ans = 1e12 + 1
    for i in range(1, int(sqrt(N)) + 1):
        if N % i == 0:
            j = N // i
            ans = min(ans, i + j - 2)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N = int(input())
N_ = int(math.sqrt(N)) + 1

min_distance = N - 1
for i in range(1, N_):
    p, r = divmod(N, i)
    if r == 0:
        if 1 <= p <= N:
            distance = (i-1) + (p-1)
            min_distance = min(min_distance, distance)
        else:
            continue

print(min_distance)

Submission status: Accepted

Solution code:
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def resolve():
    n = int(input())
    ans = float('inf')
    c = divisor(n)
    for a in c:
        b = n//a
        ans = min(ans,a+b-2)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
N=int(input())
ans=N*2-2
for n in range(1,int(N**.5)+1):
	if N%n==0:
		ans=min(ans,N//n+n-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:
        a=i
        b=n//i
        break
print(a-1+b-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
ans = float('inf')

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
m = 10**13
for x in range(1,1000001):
  y = n / x
  if y % 1 == 0:
    v = x + y -2
    m = min(m, v)
print(int(m))

Submission status: Accepted

Solution code:
from math import sqrt
n = int(input())
minSoFar = 10**12+1

for a in range(1, int(sqrt(n))+1):
    if n % a == 0:
        b = n // a
        minSoFar = min(minSoFar, a+b-2)
print(minSoFar)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

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()
m=len(divisors)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N = int(input())

def low_divisors(N):
  K=1
  low_divs = []
  while K*K <= N:
    if N%K == 0:
      low_divs.append(K)
    K += 1

  return low_divs

L_divs = low_divisors(N)
D = []

for i in range(len(L_divs)):
  D.append(L_divs[i]+N//L_divs[i])
  
print(min(D)-2)

Submission status: Accepted

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

ans = float("inf")
flag = 0
for i in range(2,int(n**(1/2))+1):
  if n%i == 0:
    ans = min(ans, i+(n//i)-2)
    flag = 1

if flag:
  print(ans)
else:
  print(n-1)

Submission status: Accepted

Solution code:
n = int(input())
#a, b, c, x, y = map(int, input().split())
#al = list(map(int, input().split()))
#al=[list(input()) for i in range(n)]
x = 1
mn = n-1
while x**2 <= n:
    if n % x == 0:
        y = n//x
        mn = min(mn, x+y-2)
    x+=1
    
print(mn)

Submission status: Accepted

Solution code:
def abc144c_walk_on_multiplication_table():
    def divisor(n):
        """ nの約数列挙 """
        ret = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                ret.append(i)
                if i ** 2 == n:
                    continue
                ret.append(n // i)
        return ret  # sortされていない
    ans = float('inf')
    n = int(input())
    a = divisor(n)
    for item in a:
        ans = min(ans, item-1+n//item-1)
    print(ans)
abc144c_walk_on_multiplication_table()

Submission status: Accepted

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

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

    j = n//i
    ans = min(ans,(i-1)+(j-1))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
c = n-1
for i in range(1,int(n**0.5)+1):
  if (n/i).is_integer():
    j = n//i
    c = min(c, i+j-2)
print(c)

Submission status: Accepted

Solution code:
from math import sqrt as s

N = int(input())
x, y = [], []
for i in range(1, int(s(N))+1):
  if N % i == 0:
    x.append(i)
    y.append(N // i)

ans, M = float("INF"), len(x)
for i in range(M):
  ans = min(ans, x[i] + y[i] - 2)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = int(input())

yakusu_list = make_divisors(N)
if len(yakusu_list)%2 == 1:
    ans = (yakusu_list[len(yakusu_list)//2]-1)*2
else:
    ans = yakusu_list[len(yakusu_list)//2-1] - 1 + yakusu_list[len(yakusu_list)//2] - 1

print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
M = []
sqr_N = math.floor(math.sqrt(N))
a = 0
    
for i in range(1, (sqr_N + 1)):
    if N % i == 0:
        a = i

a_pair = N // a
print(a + a_pair - 2)

Submission status: Accepted

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

top = int(math.sqrt(n))
a = 1

for x in range(1,top+1):
  if n % x == 0:
    a = x
    
a_pair = n // a
print(a + a_pair -2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def make_divisors(n):
    '''
    nの約数の配列を返す
    '''
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def solve():
    N = int(input())
    D = make_divisors(N)
    ans = N - 1
    for d in D:
        ans = min(ans, N // d - 1 + d - 1)
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# row = [int(x) for x in input().rstrip().split(" ")]
# n = int(input().rstrip())
# s = input().rstrip()

def make_divisors(n: int):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors, upper_divisors[::-1]



def resolve():
    import sys
    input = sys.stdin.readline

    n = int(input().rstrip())
    lower_divisors, _ = make_divisors(n)
    print(min(lower_divisor + (n // lower_divisor) - 2 for lower_divisor in lower_divisors))





if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math

n = int(input())

def p(x):
  if x == 2:
    return True
  for i in range(2,int(math.sqrt(x))+1):
    if x % i == 0:
      return False
  return True

def check(x):
  res = 10 ** 12
  for i in range(2,int(math.sqrt(x))+1):
    if x % i == 0:
      s = (i-1) + (x//i -1)
      res = min(res,s)
  return res

if p(n):
  print(n-1)
else:
  print(check(n))

Submission status: Accepted

Solution code:
N=int(input())

ans=N*2
i=1
while i*i<=N:
    if N%i==0:
        ans=min(ans,N//i+i)
    #print(ans,i+N//i)
    i+=1
    
print(ans-2)

Submission status: Accepted

Solution code:
import math

def main():
    N = int(input())
    ans = N
    for i in range(1, int(math.sqrt(N)) + 1):
        if N % i != 0:
            continue
        j = N // i
        d = (i - 1) + (j - 1)
        if d < ans:
            ans = d
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
mini = float('inf')

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

print(mini - 2)

Submission status: Accepted

Solution code:
n=int(input())
m=10**12
for i in range(1,10**6+1):
  if n%i==0:
    m=min(m,i+(n//i))

print(m-2)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
import math
n=int(input())
ans=n
for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
        a=i
        b=int(n/i)
        if a+b-2<ans:
            ans=a+b-2
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
import math
n=int(input())
ans=n
for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
        a=i
        b=int(n/i)
        if a+b-2<=ans:
            ans=a+b-2
print(ans)

Submission status: Accepted

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

# (1, 1)から(a, b)に至るまでの移動回数は(a+b−2)であることに注意すると、
# a*b=N を満たす(a, b)について(a+b−2)の最小値を求めればよい
# 対称性より、O(√N)
# 今回はN=O(10^12)なので間に合う

# a+b-2の最小値を求める
ans = N-1
for i in range(1, int(math.sqrt(N))+1):
  if N % i == 0:
    ans = min(ans, (N//i)+i-2)
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

m = 10**12
for i in range(1, 10**6+1):
  if N % i == 0:
    m = min(m, i + (N // i))
    
    
print(m-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:
                ans = min(ans,i+n//i-2)
        else:
          continue
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 01:55:56 2020

@author: liang
"""

import math
N = int(input())
key = int(math.sqrt(N))

ans = 10**12
for i in reversed(range(1,key+1)):
    if N%i == 0:
        ans = i-1 + N//i -1
        break
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline

    n = int(readline())
    a = int(n**(1/2)//1)
    for i in range(a, 0, -1):
        b, m = divmod(n, i)
        if m == 0:
            print(i+b-2)
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def div(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
  import functools
  import operator
  import numpy as np
  import itertools
  import math
  lis = [1]
  N = int(input())
  x = div(N)
  A = []
  for i in range(math.ceil(len(x)/2)):
    A.append(x[i]+x[len(x)-i-1])
  ans = min(A)-2
  print(ans)
main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
d = 10**20
for a in range(1,int(N ** 0.5)+1):
  if N % a == 0:
    b = N // a
    c = a + b - 2
    if d > c:
      d = c
print(d)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n = int(input())
#探索範囲
sqrt_n = int(math.sqrt(n))
num_i = 0
for i in range(1, sqrt_n+1):
    if n % i == 0:
       num_i = i

num_j = n // num_i
ans = (num_i - 1) + (num_j - 1)

print(ans)

Submission status: Accepted

Solution code:
import math

ans = 1000000000000000000
N = int(input())
for i in range(math.ceil(math.sqrt(N+1000))):
  if i > 0 and N % i == 0:
    ans = min(i + N/i - 2, ans)
print(int(ans))

Submission status: Accepted

Solution code:
import math

N = int(input())
ans = 10**12

for i in range(1,math.ceil(math.sqrt(N))+2):
    if N % i == 0:
        tem = N//i + N//(N//i) -2
        if tem <= ans:
            ans = tem

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import functools as fts
import itertools as its
import math
import sys

INF = float('inf')


def solve(N: int):
    def manhattan_distance(x1, y1, x2, y2):
        return abs(x1-x2) + abs(y1-y2)
    return min(manhattan_distance(1, 1, i, N//i) for i in range(1, int(math.sqrt(N))+1) if N % i == 0)


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    print(f'{solve(N)}')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

input = sys.stdin.readline
n = int(input())

yaku_list = make_divisors(n)
index = int(len(yaku_list)/2)


if len(yaku_list) % 2 == 0:
    result = yaku_list[index-1] - 1 + yaku_list[index] - 1 
else:
    result = yaku_list[index] - 1 + yaku_list[index] - 1 

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
ans=float('inf')
a=1
while n**0.5>=a:
  if n%a==0:
    ans=min(ans,a+n//a-2)
  a+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

ans = float("inf")
for i in range(1, int(n**0.5)+1):
  if n%i == 0:
    t = n//i
    if i-1+t-1 < ans: ans = i-1+t-1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    ans=N
    
    M=10**6+5
    for i in range(1,M):
        if N%i==0:
            j=N//i
            temp=i+j-2
            ans=min(ans,temp)
            
    print(ans)
            
        

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

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

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

    ans = 1e18
    for i in range(1, N + 1):
        if i * i > N:
            break
        if N % i != 0:
            continue
        j = N // i
        ans = min(ans, i + j - 2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
x = int(N**0.5)+1
ans_1 = N

for i in range(x):
    if N % x == 0:
        ans_1 = x
        break
    else:
        x -= 1

ans_2 = N//ans_1
print(ans_1 + ans_2 - 2)

Submission status: Accepted

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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

if cnt == 0:
  ans = n-1
print(int(ans))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N = int(readline())

    def enum_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

    divs = enum_divisors(N)

    ans = INF
    for div1 in divs:
        div2 = N // div1
        score = (div1 + div2 - 2)
        ans = min(score, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

divisors = []

i = 1
while i*i <= N:
    if N % i == 0:
        divisors.append(i)
    i += 1

print(divisors[-1] + N // divisors[-1] - 2)

Submission status: Accepted

Solution code:
n = int(input())
ans = (0, n)
for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        ans = min(ans, (i, n // i), key=lambda x: abs(x[0] - x[1]))
print(ans[0] - 1 + ans[1] - 1)

Submission status: Accepted

Solution code:
# 問題: https://atcoder.jp/contests/abc144/tasks/abc144_c

import math

n = int(input())
a = int(math.sqrt(n))
b = 0
while b == 0:
    if n % a > 0:
        a -= 1
        continue
    b = n / a

res = a + b - 2
print(int(res))

Submission status: Accepted

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


N = I()
for i in range(int(N**.5),0,-1):
    if N % i == 0:
        print(i+(N//i)-2)
        exit()

Submission status: Accepted

Solution code:
import math
N=int(input())
a=1
sum=N
flag=True
while flag:
    if a>math.sqrt(N):
        break
    if N%a==0:
        b=N//a
        if sum>a+b-2:
            sum=a+b-2
    a+=1
print(sum)

Submission status: Accepted

Solution code:
N = int(input())
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
mdn = make_divisors(N)

aa = []
for x in mdn:
  aa.append(x+N//x)
print(min(aa)-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
n = I()
def yaku(m):
    ans = []
    i = 1
    while i*i <= m:
        if m % i == 0:
            j = m // i
            ans.append(i)
        i += 1
    ans = sorted(ans)
    return ans
a = yaku(n)
#print(a)
ans = float('inf')
for v in a:
    ans = min(ans, (v-1)+(n//v)-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

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

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

n = I()

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

ans = make_divisors(n)
# print(ans)

m = INF
for i in range(len(ans)//2+1):
    c = ans[i] - 1 + ans[-i-1] - 1
    # print(c)
    m = min(m,c)
print(m)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

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


N = int(input())
divs = enum_divisors(N)
ans = float("inf")
for div in divs:
    ans = min(ans, div + N // div - 2)
print(ans)

Submission status: Accepted

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

    divisors.sort()
    return divisors

d = make_divisors(n)
ans = 10**18
for a in d:
    ans = min(ans, n//a-1+a-1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = int(n**0.5)
while n%x!=0: x-= 1
y = n//x
print(x-1+y-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
for i in range(int(N**.5),0,-1):
    if N % i == 0:
        print(i+(N//i)-2)
        exit()

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(i+N//i-2,ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = prime_factorize(N)
if c[-1] > 10**6:
    print(c[-1] + N//c[-1] - 2)
    exit()

while 1:
    if a*b < N:
        a += 1
    elif a*b > N:
        b -= 1
    else:
        print(a+b-2)
        exit()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

import math

n = math.sqrt(N)

if n.is_integer() == True:
  print(int(2*n - 2))
  exit()
else:
  c = math.floor(n)
  for i in range(0, c):
    d = c - int(i) 
    e = N / d
    if e.is_integer() == True:
      print(int(d + N/d - 2))
      exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())

ans=10**12
d=2
while d<=n**(1/2):
    if n%d==0:
        ans=min(ans,d+n//d-2)
    d+=1
if ans==10**12:
    print(n-1)
    exit()
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N=int(input())
i=math.ceil(math.sqrt(N))
while True:
    if N%i == 0:
        break
    else:
        i -= 1
j = N // i
print(i-1+j-1)

Submission status: Accepted

Solution code:
n = int(input())

i = 1
l = []

while i * i <= n:
    if n % i == 0:
        l.append(i)
    i += 1

a = l[-1]
b = n // l[-1]
ans = a + b - 2
print(ans)