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: Wrong Answer

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

N = int(input())

prime_L = prime_factorize(N)
n = len(prime_L)
sum = 10 ** 13

for i in range(2 * n):
    bit = str(format(i, 'b')).zfill(n)
    total_a = 1
    total_b = 1
    for j in range(n):
        if bit[j] == '0':
            total_a = total_a * prime_L[j]
        elif bit[j] == '1':
            total_b = total_b * prime_L[j]
    if total_a + total_b - 2 < sum:
        sum = total_a + total_b - 2
print(sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import os

def main():
	n = int(input())
	list_a = make_divisors(n)
	min_num = 1000000000000
	print(list_a)
	for i in range(0,len(list_a),2):
		if n//list_a[i] == list_a[i]:
			min_num = list_a[i] * 2 - 2
			break
		if min_num < (list_a[i] + list_a[i+1] - 2):
			pass
		else:
			min_num = list_a[i] + list_a[i+1] - 2
	print(min_num)
	
			


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

	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import os

def main():
	n = int(input())
	list_a = make_divisors(n)
	min_num = 1000000000000
	for i in range(0,len(list_a),2):
		if len(list_a) <= i + 1:
			break
		if min_num < (list_a[i] + list_a[i+1] - 2):
			pass
		else:
			min_num = list_a[i] + list_a[i+1] - 2
	print(min_num)
	
			


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

	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
n_list = []
for i in range(1, int(math.sqrt(n))):
    if n % i == 0:
        n_list.append((i, n//i))
sa = n-1
for x, y in n_list:
    if sa >= abs(x-1)+abs(y-1):
        sa = abs(x-1) + abs(y-1)
print(sa)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
n_list = []
for i in range(1, int(math.sqrt(n))):
    if n % i == 0:
        n_list.append((i, n//i))
sa = n-1
for x, y in n_list:
    if sa >= abs(x-1)+abs(y-1):
        sa = abs(x-1) + abs(y-1)

print(sa)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
n_list = []
for i in range(1, int(math.sqrt(n))):
    if n % i == 0:
        n_list.append((i, n//i))
sa = 10**13
for x, y in n_list:
    if sa >= abs(x-1)+abs(y-1):
        sa = abs(x-1) + abs(y-1)

print(sa)

Submission status: Wrong Answer

Solution code:
n = int(input())
if n >= 2:
     nm = [2]
     for i in range(3, n + 1):
         for p in nm:
             if i % p == 0:
                 break
         else:
             nm.append(i+n//i-2)
print(max(nm))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def intinp():
    return int(input())

N = intinp()

l = []
for i in range(1, 10**6):
    j = N/i
    if j.is_integer():
        l.append(tuple([i, j]))

ans = 10**13
for v in l:
    t = v[0]+v[1]-2
    if t < ans:
        ans = t

print(int(ans))

Submission status: Wrong Answer

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

def intinp():
    return int(input())

N = intinp()

l = []
for i in range(1, 10**6):
    j = N/i
    if j.is_integer():
        l.append(tuple([i, j]))

ans = 10**13
for v in l:
    print(v)
    t = v[0]+v[1]-2
    if t < ans:
        ans = t

print(int(ans))

Submission status: Wrong Answer

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

def intinp():
    return int(input())

N = intinp()

l = []
for i in range(1, 10**6):
    j = N/i
    if j.is_integer():
        l.append(tuple([i, j]))

ans = 10**12
for v in l:
    t = v[0]+v[1]-2
    if t < ans:
        ans = t

print(int(ans))

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

print(cnt + n//cnt - 2)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 1 + N - 2 #求めるのは(x-1) + (y-1)の最小値
for i in range(1, int(N**0.5)):
    if N%i==0:
        ans = min(ans, i+N//i-2)
print(ans)

Submission status: Wrong Answer

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

a = int(input())
x = []
x = make_divisors(a)
print(x[len(x)//2-1]+x[len(x)//2]-2)

Submission status: Wrong Answer

Solution code:
from math import ceil, sqrt

n = int(input())

ans = n - 1
for i in range(2, ceil(sqrt(n))):
    j, mod = divmod(n, i)
    if mod == 0:
        temp = i + j - 2
        if temp < ans:
            ans = temp
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
import math
for i in range(2, 53):
    if N % i == 0:
        A.append(i)

if len(A) == 0:
    print(N-1)
    exit()
C = range(2,N)
B = 10 **13
for a in range(int(math.sqrt(N)) + 1, 1, -1):
    if N % a == 0:
        print(a + (N // a) - 2)
        break

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
import math
for i in range(2, 53):
    if N % i == 0:
        A.append(i)

if len(A) == 0:
    print(N-1)
    exit()
C = range(2,N)
B = 10 **13
for a in range(int(math.sqrt(N)) + 1, 1, -1):
    if N % a == 0:
        print(int(a + (N / a) - 2))
        break

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
import math
for i in range(2, 53):
    if N % i == 0:
        A.append(i)

if len(A) == 0:
    print(N-1)
    exit()
C = range(2,N)
B = 10 **13
for a in range(int(math.sqrt(N)), 1, -1):
    if N % a == 0:
        print(int(a + (N / a) - 2))
        break

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(2, 53):
    if N % i == 0:
        A.append(i)

if len(A) == 0:
    print(N-1)
    exit()

B = []
for a in A:
    B.append((a + (N / a) - 2))

C = min(B)
print(int(C))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(2, 53):
    if N % i == 0:
        A.append(i)

if len(A) == 0:
    print(N-1)
    exit()
B = []
for a in A:
    B.append((a + (N / a) - 2))

C = min(B)
print(int(C))

Submission status: Wrong Answer

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

def myAnswer(N:int) -> int:
   divisors = make_divisors(N)
   length = len(divisors)
   if(length % 2 == 1):
      return divisors[length//2] - 2
   else:
      return divisors[length//2] + divisors[length//2 - 1] - 2



def modelAnswer():
   tmp=1
def main():
   N = int(input())
   print(myAnswer(N))
if __name__ == '__main__':
   main()

Submission status: Wrong Answer

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

def myAnswer(N:int) -> int:
   divisors = make_divisors(N)
   length = len(divisors)//2
   return divisors[length] + divisors[length - 1] - 2



def modelAnswer():
   tmp=1
def main():
   N = int(input())
   print(myAnswer(N))
if __name__ == '__main__':
   main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
s =N+1
n = int(N**0.5) 
i = 1
while i<n:
  if N % i != 0:
    i += 1
  elif N % i == 0 and N//i +i < s:
    s = N//i + i
    i += 1
  else:
    i += 1
print(s-2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
import math
start = math.floor(math.sqrt(n))
for i in reversed(range(start)):
    if i == 0:
        i = n
    else:
        if n/i == int(n/i):
            break
print(i+n//i-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
 
count = 1*10^13
for _ in range(1,n+1):
  sho = n // _
  amari = n % _
  tmp_value = _ + sho -2
  if amari == 0 and tmp_value < count:
    if tmp_value > count:
      break
    count = tmp_value
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

count = 1*10^13
for _ in range(1,n+1):
  sho = n // _
  amari = n % _
  tmp_value = _ + sho -2
  if amari == 0 and tmp_value < count:
    count = tmp_value
print(count)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

minimum = None
for i in range(1, int(math.sqrt(N + 1))):
    is_dividable = N % i == 0
    if is_dividable:
        j = int(N / i)
        foo = i + j - 2
        minimum = foo if minimum is None else min(minimum, i + j - 2)

print(minimum)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
minimum = N*20
for i in range(1, round(math.sqrt(N))):
  a = i
  if N % i == 0:
    b = N // a
    if (a + b - 2) < minimum:
      minimum = (a + b - 2)

print(minimum)

Submission status: Wrong Answer

Solution code:
N = int(input())
ls = []
for i in range(9, 0, -1):
  if N % i == 0:
    ls = [i, N//i]
    break

if len(ls) == 0:
  print(N-1)
else:
  print((ls[0]-1) + ls[1] - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
ls = []
for i in range(2, 10):
  if N % i == 0:
    ls = [i, N//i]

if len(ls) == 0:
  print(N-1)
else:
  print((ls[0]-1) + ls[1] - 1)

Submission status: Wrong Answer

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

N = int(input())

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

print(ans)

Submission status: Wrong Answer

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

min = n + 1

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

print(min)

Submission status: Wrong Answer

Solution code:
n = int(input())
#  = list(map(int, input().split()))
#x = list(map(int, input().split()))
i = 1
l = []
while i*i <= n:
    if n%i==0:
        l.append(i)
        l.append(n//i)
    i+=1
l = list(set(l))
l.sort()
a = l[len(l)//2]
b = l[len(l)//2-1]
print(a+b-2)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())

ans = N-1 # Nが素数の場合はこれが答え

# 試し割法　O( 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

def souseki(numList):
    res = 1
    for i in numList:
        res *= i
    return res

# L = np.array(prime_factorize(N))
L = prime_factorize(N)

if len(L)==0:
    print(ans)
    exit()

for i in range(1, len(L)):
    a = souseki(L[:i])
    b = souseki(L[i:])

    ans = min(ans,a+b-2)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())

ans = N-1 # Nが素数の場合はこれが答え

# 試し割法　O( 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


L = np.array(prime_factorize(N))

if len(L)==0:
    print(ans)
    exit()

for i in range(1, len(L)):
    a = np.prod(L[:i])
    b = np.prod(L[i:])

    ans = min(ans,a+b-2)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def make_diviser(n):
  D=[]
  for i in range(1,int(n**0.5)+2):
    if n%i==0:
      D.append(i)
      D.append(n//i)
  D=sorted(set(D))
  l=len(D)
  if l%2==0:
    return D[(l//2)-1]+D[l//2]
  else:
    return D[l//2]**2
n=int(input())  
print(make_diviser(n)-2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

fact = factorization(N)
if len(fact)==1:
    print(N-1)
else:
    ans = 0
    youso = []
    x, y = 1, 1
    for i in fact:
        for j in range(i[1]):
            youso.append(i[0])
    if len(youso)<=2:
        ans = sum(youso)-2
    else:
        for i, num in enumerate(youso):
            if i%2==0:
                x *= num
            else:
                y *= num
        ans = x+y-2
    print(ans)

Submission status: Wrong Answer

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

p = make_divisors(n)
ans = float("inf")
for i in range(len(p)):
    if i < len(p) - 1:
        if p[i] * p[i+1] == n:
            ans = min(ans, p[i]-1+p[i+1]-1)
        elif p[i] * p[i]:
            ans = min(ans, (p[i] - 1) * 2)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
from itertools import combinations

int1 = lambda x: int(x) - 1
def II(): return int(input())

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

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


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 solve():
    n = II()
    divisors = make_divisors(n)

    ans = 1001001001001
    for a, b in combinations(divisors, 2):
        if a * b != n:
            continue
        step = (a-1) + (b-1)
        ans = min(step, ans)
    print(ans)



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
m=math.ceil(math.sqrt(n))
list=[]

for i in range(1,m):
  if n%i==0:
    s=n//i
    t=s+i
    list.append(t)
list.sort()
print(list[0]-2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = N

for a in range(2, int(N**0.5)):
    tmp = 0
    if N % a == 0:
        tmp = N//a + a
        if ans > tmp:
            ans = tmp

if ans < N:
    print(ans - 2)
else:
    print(N - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = N

for a in range(2, int(N**0.5)):
    tmp = 0
    if N % a == 0:
        tmp = N//a + a
        if ans > tmp:
            ans = tmp

if ans < N:
    print(ans - 2)
else:
    print(ans - 1)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for i in range(1,n):
    sur = n%i
    ans = n/i
   # print(i,ans,sur)
    if ans < i:
        break
    elif sur == 0:
        l.append(i)
l.sort(reverse=True)
max = l[0]
max_op = n/max
ite = max-1+max_op-1
print(ite)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
n = round(math.sqrt(N))
counter = 0
for i in range(n):
		if N%(n-i) == 0 and counter == 0:
			counter+=1
			var1=(n-i)
			var2=N/(n-i)
            
print(var1+var2-2)

Submission status: Wrong Answer

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

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

print(int(ans))

Submission status: Wrong Answer

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

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

print(int(ans))

Submission status: Wrong Answer

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

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

print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import heapq


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


n = int(readline())
memo = prime_decomposition(n)
if len(memo) == 1:
    print(memo[0] - 1)
else:
    heapq.heapify(memo)
    x, y = 1, memo.pop(-1)
    for i in range(len(memo)):
        if x > y:
            y *= heapq.heappop(memo)
        else:
            x *= heapq.heappop(memo)
    print(x + y - 2)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import heapq


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


n = int(readline())
memo = prime_decomposition(n)
if len(memo) == 1:
    print(memo[0] - 1)
else:
    heapq.heapify(memo)
    x, y = 1, 1
    for i in range(len(memo)):
        if x > y:
            y *= heapq.heappop(memo)
        else:
            x *= heapq.heappop(memo)
    print(x + y - 2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
x=[]
min=10000000
ans=0
for i in range(1,N+1):
  for j in range(1,N-i+1):
    if i*j==50:
      a=[i,j]
      x.append(a)
for i,j in x:
  if i+j<=min:
    ans=i+j-2
    min=i+j
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
import math
a=math.floor(math.sqrt(n))
while a>0:
  if n%a==0:break
  a-=1

print(a+n//a)

Submission status: Wrong Answer

Solution code:
n=int(input())
c=10**9
for i in range(1,n//2):
    if n%i==0:
        j=n/i
        if i+j < c:
            c=int(i+j)

print(c-2)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

ans = 10**15
for k in range(1, int(math.sqrt(N))):
    if N % k > 0:
        continue
    ans = min(ans, k + N//k - 2)
print(ans)

Submission status: Wrong Answer

Solution code:
def get_divisors(n):
    res = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n//i)
    return sorted(res)
    
N = int(input())
ds = get_divisors(N)

res = 10**12

print('len(ds) = ', len(ds))

if len(ds) % 2 != 0:
    # 平方数の場合
    for i in range((len(ds)+1) // 2):
        res = min(res, ds[i] + ds[-(i+1)])
else:
    # 平方数でない場合
    for i in range(len(ds) // 2):
        print(ds[i], ds[-(i+1)])
        res = min(res , ds[i] + ds[-(i+1)])
        
print(res - 2)

Submission status: Wrong Answer

Solution code:
#--------------------------------------------
#ライブラリ等
import sys
import math
from math import sqrt
input = sys.stdin.readline

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

Submission status: Wrong Answer

Solution code:
import array
import sys
from collections import deque
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
#S = deque(list(input()))

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
min = 9999999999999
for i in range(2, N):
  if N % i == 0:
    x = (N//i)+i-2
    min = x if x < min else min
print(min)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

ans = pow(10, 30)
for i in range(1, int(pow(n, 0.5)) + 1):
    for j in range(i, n):
        #print(i, j)
        if i * j == n and i + j - 2 < ans:
            ans = i + j - 2
print(ans)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

a = math.floor(math.sqrt(N))

while N % a != 0:
    a -= 1

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def prime(n):
    for k in range(2,int(math.sqrt(n)+1)):
        if n!=k and n%k==0:
            return False
    return True
#素数判定

ans=0
if prime(n)==True:
    ans=n-1
else:
    for k in range(n-int(math.sqrt(n)+1)):
        print('k',k)
        if n%(n-k)==0:
            ans=(n-k-1)+(n//(n-k)-1)
            
print(ans)

Submission status: Wrong Answer

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

m = 99999999
pair = [0,0]
for i in range(1,int(math.sqrt(N))+1):
    if N % i == 0:
        if int(N/i) - i < m:
            m = int(N/i) - i
            pair = [int(N/i),i]

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def trial_division(n):
  factors = []
  f = 2
  while f**2 <= n:
    if n % f == 0:
      n //= f
      factors.append(f)
    else:
      f += 1
  if n != 1:
    factors.append(n)
  return factors

N = int(input())
factors = trial_division(N)

if len(factors) == 1:
  print(factors[0]-1)
else:
  a = 1
  b = 1
  for f in reversed(factors):
    if a <= b:
      a *= f
    else:
      b *= f
  print(a+b-2)

Submission status: Wrong Answer

Solution code:
def trial_division(n):
  factors = []
  f = 2
  while f**2 <= n:
    if n % f == 0:
      n //= f
      factors.append(f)
    else:
      f += 1
  if n != 1:
    factors.append(n)
  return factors

N = int(input())
factors = trial_division(N)

if len(factors) == 1:
  print(factors[0]-1)
else:
  a = 1
  b = 1
  for f in factors:
    if a <= b:
      a *= f
    else:
      b *= f
  print(a+b-2)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul


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

N = int(input())
factors = trial_division(N)

if len(factors) == 1:
  print(factors[0]-1)
else:
  res = N**2
  for i in range(len(factors)-1):
    a = reduce(mul, factors[:i+1])
    b = reduce(mul, factors[i+1:])
    if a+b-2 < res:
      res = a+b-2
  print(res)

Submission status: Wrong Answer

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
lis=make_divisors(n)
print(lis[-1]+lis[-2]-2)

Submission status: Wrong Answer

Solution code:
N = int(input())


def divisors(n):
    ret = set()
    for i in range(1, int(n**(0.5))):
        if n % i == 0:
            ret.add(i)

    return(ret)


ans = N-1
for x in divisors(N):
    ans = min(ans, x-1+(N//x)-1)

print(ans)