Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

10

Sample Output 1

5

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

Sample Input 2

50

Sample Output 2

13

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

Sample Input 3

10000000019

Sample Output 3

10000000018

Both input and output may be enormous.



Sample input:
10


Sample output:
5

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    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()
    l = len(divisors)
    if l % 2 == 0:
        print(divisors[l//2] + divisors[l//2-1] - 2)
    else:
        print(2 * divisors[l//2]- 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

import math
for a in range(int(math.sqrt(n)) + 1, 0, -1):
  b = n // a
  if a * b == n:
    print(a - 1 + b - 1)
    exit(0)

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
input = sys.stdin.readline

setrecursionlimit(1000000)

dp = defaultdict(lambda x:-1)

def main():
	n = int(input())
	i = int(math.sqrt(n)) + 1
	while True:
		if(n % i == 0):
			print(n//i + i - 2)
			return
		i -= 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 zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

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

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

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 + n//i)
    return divisors


n = int(input())
divs = make_divisors(n)
print(min(divs)-2)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())
ans = float("INF")
for i in range(1, 1000100):
  if (n%i == 0):
    j = n//i
    ans = min(ans, i+j-2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getDivisors(x):
    anss = set()
    for d in range(1, int(x**0.5)+1):
        if x%d == 0:
            anss.add(d)
            anss.add(x//d)
    return sorted(anss)

N = int(input())

divs = getDivisors(N)

ans = N
for div in divs:
    num = div + N//div - 2
    ans = min(ans, num)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())
n = int(sqrt(N))
ans = 10 ** 25
for i in range(1, n + 1):
    if N % i == 0:
        j = N // i
        #print('i={}, j={}'.format(i, j))
        ans = min(ans, i + j - 2)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ans = float('inf')
for i in range(10**6):
  a = i+1
  if(N%a == 0):
    b = N//a
    dist = abs(a-1)+abs(b-1)
    ans = min(ans,dist)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

p = int(n ** 0.5)

while p > 1:
    #print(p, n // p, n % p)
    if n % p == 0:
        print(p + (n // p) - 2)
        exit()
    p -= 1

print(n-1)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N = int(input())

a = int(N**0.5)

b = -1
while b==-1:
	if N%a==0:
		b = N//a
		break
	a -= 1

ans = a+b-2
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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

Submission status: Accepted

Solution code:
n=int(input())
arr=[1]
from math import sqrt as S 
for i in range(2,int(S(n))+1):
    if n%i==0: 
        arr.append(i)
mini=10**20 
for a in arr: 
    b=n//a 
    mini=min(mini,a+b-2)
print(mini)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()

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

print(res+(n//res)-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


def resolve():
    n = int(input())
    l = make_divisors(n)
    print(min([x + (n // x) for x in l]) - 2)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time

setrecursionlimit(10**6)
input=stdin.readline

n=int(input().rstrip())
a,b=1,n
for i in range(int(n**0.5)+1,-1,-1):
    if n%i==0:
        a,b=i,n//i
        break
print(a-1+b-1 if a!=1 else b-1)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
n=int(input())
def div(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
ans=div(n)
ans.sort()
m=len(ans)
if(m%2==1):
    a=ans[m//2]
    b=ans[m//2]
else:
    a=ans[m//2-1]
    b=ans[m//2]
print(a+b-2)

Submission status: Accepted

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

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:
#C
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())
lst=make_divisors(n)
ans=float("inf")
for u in lst:
    ans=min(ans,u+n//u-2)
print(ans)

Submission status: Accepted

Solution code:
def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1+div2-2)
    array.sort()
    return array

n = int(input())
ans = min(divisors(n))
print(ans)

Submission status: Accepted

Solution code:
from math import *

n = int(input())
sn = int(sqrt(n))
a, b = 0, 0

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

Submission status: Accepted

Solution code:
def main():

    n = int(input())
    cnt = n
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = min(cnt, i + n / i - 2)
    print(int(cnt))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

print(ans-2)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

Submission status: Accepted

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


def main():
  n = int(input())
  s = n

  for i in range(1, n):
    if i ** 2 > n:
      break

    if n % i != 0:
      continue

    s = min((i - 1) + (n // i - 1), s)

  print(s)


if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

    divisors.sort()
    return divisors

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

    divisors = make_divisors(N)

    mi = float("inf")
    for v in divisors:
        x = N // v
        mi = min(mi, x + v - 2)

    print(mi)

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())


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

    return min(divisors)


print(solve(N))

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    def yakusuu(a):
        yakusuu=set()
        for i in range(1,int(a**0.5)+1):
            if a%i==0:
                yakusuu.add(i)
                yakusuu.add(a//i)
        yakusuu=sorted(list(yakusuu))
        return yakusuu
    y=yakusuu(n)
    print(min([i+(n//i)-2 for i in y]))
        
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N = int(input())

i = 1
min_num = 10000000000000000
while i <= N**0.5 + 1:
	if N % i == 0:
		min_num = min(min_num, i + N//i)
	i += 1

print(min_num - 2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
divs = []
for i in range(1, int(n**0.5) + 1):
    if n % i == 0:
        divs.append(i)
d = divs[-1]
print(d - 1 + n // d - 1)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import array
import math
import os
import sys


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


def solve(N):
    best = N - 1
    x = 2
    while x * x <= N:
        if N % x == 0:
            y = N // x
            best = min(best, x + y - 2)
        x += 1
    return best


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())

def check(N):
	n2 = math.floor(math.sqrt(N))
	min = N - 1
	for i in range(2, n2 + 1):
		if N % i == 0:
			j = N // i
			d = i + j - 2
			if d < min:
				min = d
	return min

print(check(N))

Submission status: Accepted

Solution code:
import math
import itertools

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

a, b = 0, 0

M = N ** (1 / 2) + 1
M = int(M)

for i in range(1, M + 1):

    if N % i == 0:
        a, b = i, N // i


print(a + b - 2)

Submission status: Accepted

Solution code:
from math import sqrt
N = int(input())
ans = float("inf")
for k in range(1,int(sqrt(N)+1)+1):
    if N%k == 0:
        ans = min(ans,k-1+N//k-1)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

rN = int(pow(N,1/2) + 1)

res = 1
for i in range(1,rN):
    if N % i == 0:
        res = i

ans = res + N // res - 2

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def yakusuu(N):
    ret1 = []
    ret2 = []
    for i in range(1,int(N**0.5)+1):
        if N%i==0:
            ret1.append(i)
            ret2.append(N//i)
    return ret1,ret2

X,Y = yakusuu(N)

ans = 10**13
for i,x in enumerate(X):
    y = Y[i]
    ans = min(ans,abs(x-1)+abs(y-1))
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

l=make_divisors(n)
m=len(l)
if m%2==0:
    print(l[m//2-1]+l[m//2]-2)
else:
    print(2*l[m//2]-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

# n
# a, b = list(map(int, input().split()))
# s = input()

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

print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
tmp=pow(n,0.5)
tmp=int(tmp)
cnt1=0
cnt2=0
for i in range(tmp):
    if n%(tmp-i)==0:
        cnt1=n//(tmp-i)
        cnt2=tmp-i
        break
print(cnt1+cnt2-2)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt

n = ni()
ans = n-1

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

n_sq = int(n**(1/2))
fact = []
for i in range(1,n_sq+2):
    if n%i == 0:
        fact.append(i)
ans = n-1
for i in fact:
    if n//i + i-2<ans:
        ans = n//i +i-2
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
# from bisect import *
# from collections import *
# from heapq import *
# import itertools
import math
# INF = 10**9
# MOD = 10**9+7

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

Submission status: Accepted

Solution code:
n = int(input())

def get_divisors(num):
    divs = []
    for i in range(1, int(num**0.5)+1):
        if not num % i:
            divs.append((i, num // i))
    return divs

ans = float("inf")
d = get_divisors(n)
for a, b in d:
    ans = min(ans, a+b-2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)

INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()

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


print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
ans = 10 ** 13
A = 1
while A ** 2 <= N:
    if N % A == 0:
        if A + (N // A) < ans:
            ans = A + (N // A)
    A += 1
print(ans - 2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N = int(input())

d = math.floor(N**(1/2))

ans = 0

for i in range(1,d+1):
	if N % i == 0:
		ans = i

ans_2 = N // ans

print(ans + ans_2 - 2)

Submission status: Accepted

Solution code:
N = int(input())
ans = 10 ** 20
for i in range(1, 10 ** 6 + 1):
    if i ** 2 > N: break
    if N % i == 0:
        ans = min(ans, i + N // i - 2)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from math import sqrt


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

    mn = float("inf")
    for i in range(1, int(sqrt(n)) + 1):
        q, r = divmod(n, i)
        if r == 0:
            mn = min(mn, i + q - 2)

    print(mn)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
import collections
class Devisor(int):
    def __init__(self, n: int):
        self.val = n

    def isprime(self):
        if self.val <= 1:
            return 0
        for i in range(2, int(math.sqrt(self.val)) + 1):
            if self.val % i == 0:
                return 0
        return 1

    def factorize(self):
        res = collections.defaultdict(int)
        n = self.val
        i = 2
        while i * i <= n:
            while n % i == 0:
                n //= i
                res[i] += 1
            i += 1
        if n != 1:
            res[n] += 1
        return res

    def divisor(self):
        n = self.val
        ret = list()
        for i in range(1, int(math.sqrt(n)) + 1):
            if n % i == 0:
                ret.append(i)
                ret.append(n // i) if i * i != n else None
        return ret

# END CUT HERE

def main():
    N = ii()
    d = Devisor(N).divisor()
    m = 10**18
    for x in d:
        if x + N // x < m:
            m = x + N // x
    print(m - 2)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

ans = n-1

d = 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from random import randint
from itertools import imap as map, izip as zip, permutations, combinations, combinations_with_replacement
from __builtin__ import xrange as range
from math import ceil
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
import sys
import os
import re
sys.setrecursionlimit(9999)
inf = float('inf')
mod = int(1e9) + 7
mod_ = 998244353
N = 5001
 
'''
Check for special cases (n=1)
One wrong submission = 10 mins penalty!
do smth instead of nothing and stay organized
'''

def main():
	n = int(input())
	ans = inf
	for i in range(1, int(n**.5)+1):
		if n%i == 0:
			curr = i + (n//i) - 2
			ans = min(ans, curr)
	print(ans)


BUFSIZE = 8192
class FastI(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = StringIO()
		self.newlines = 0
 
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()
 
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count("\n") + (not b)
			ptr = self._buffer.tell()
			self._buffer.seek(0, 2), self._buffer.write(
				b), self._buffer.seek(ptr)
		self.newlines -= 1
		return self._buffer.readline()
class FastO(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = __pypy__.builders.StringBuilder()
		self.write = lambda s: self._buffer.append(s)
 
	def flush(self):
		os.write(self._fd, self._buffer.build())
		self._buffer = __pypy__.builders.StringBuilder()
def print(*args, **kwargs):
	sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop("end", "\n"))
	if kwargs.pop("flush", False):
		file.flush()
def gcd(x, y):
	while y:
		x, y = y, x % y
	return x
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
	def bootstrap(cont):
		call, arg = cont.switch()
		while True:
			call, arg = cont.switch(to=continulet(
				lambda _, f, args: f(*args), call, arg))
	cont = continulet(bootstrap)
	cont.switch()
	main()

Submission status: Accepted

Solution code:
get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

# N = 10
# N = 50
# N = 10000000019

N = get()
x = int(N ** 0.5)
for i in xrange(x, 0, -1):
    if N / i * i == N:
        print i + N / i - 2
        exit()

Submission status: Accepted

Solution code:
N = int(input())

min_val = 10**27
for i in range(1,int(N**0.5)+1):
    if N%i==0:
        j = N//i
        min_val = min(min_val, i+j)

print(min_val-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


def main():
    N = int(input())
    ans = N - 1
    rt = int(math.sqrt(N))
    for x in range(2, rt+1):
        if N % x == 0:
            y = N // x
            ans = min(ans, (x + y - 2))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

# int(input())
# map(int, input().split())

n = int(input())

st = set()
for divisor in range(1, int(n ** 0.5) + 1):
    if n % divisor == 0:
        st.add(divisor + (n // divisor) - 2)
print(min(st))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N = int(input())

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

    # divisors.sort()
    return divisors

div = make_divisors(N)
ans = 10**13;

for i in range(len(div)):
    a = div[i]
    b = N//a
    ans = min(ans,a+b-2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


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


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

    for a in range(int(N ** 0.5) + 1, 0, -1):
        if N % a != 0:
            continue
        b = N // a
        print(a + b - 2)
        return


if __name__ == '__main__':
    f()

Submission status: Accepted

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

Submission status: Accepted

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