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: Time Limit Exceeded

Solution code:
# abc144 C
# 素因数分解してみる（これは後でちゃんと理解しておく！！！）
import numpy as np
import itertools

n = int(input())


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


# リストを2分割する
n_insu_list = prime_factorize(n)
bunkai_list = []
# for i in range(1, len(n_insu_list)):
#     bunkai_list.append((np.prod(n_insu_list[:i]), np.prod(n_insu_list[i:])))  # ここが間違っている。
# あらゆる並べ方に対して、この部屋分け的発想を試す必要がある
# n_insu_listを並べ替えたやつ
n_insu_list_list = list(itertools.permutations(n_insu_list))
for nlist in n_insu_list_list:
    for i in range(1, len(nlist)):
        bunkai_list.append((np.prod(nlist[:i]), np.prod(nlist[i:])))
bunkai_list.append((1, n))

# bunkai_listのうち、tupleの和が最小であるものを選び、そのindexを取得する。そのindexのtupleを取得し、そこまでの移動回数を調べる
bunkai_list_sum = [sum(x) for x in bunkai_list]

min_tuple = bunkai_list[bunkai_list_sum.index(min(bunkai_list_sum))]

print(sum(min_tuple) - 2)

Submission status: Time Limit Exceeded

Solution code:
# abc144 C
# 素因数分解してみる（これは後でちゃんと理解しておく！！！）
import numpy as np
import itertools

n = int(input())


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


# リストを2分割する
n_insu_list = prime_factorize(n)
bunkai_list = []
# for i in range(1, len(n_insu_list)):
#     bunkai_list.append((np.prod(n_insu_list[:i]), np.prod(n_insu_list[i:])))  # ここが間違っている。
# あらゆる並べ方に対して、この部屋分け的発想を試す必要がある
# n_insu_listを並べ替えたやつ
n_insu_list_list = list(itertools.permutations(n_insu_list))
for nlist in n_insu_list_list:
    for i in range(1, len(nlist)):
        bunkai_list.append((np.prod(nlist[:i]), np.prod(nlist[i:])))
bunkai_list = list(set(bunkai_list))
bunkai_list.append((1, n))

# bunkai_listのうち、tupleの和が最小であるものを選び、そのindexを取得する。そのindexのtupleを取得し、そこまでの移動回数を調べる
bunkai_list_sum = [sum(x) for x in bunkai_list]

min_tuple = bunkai_list[bunkai_list_sum.index(min(bunkai_list_sum))]

print(sum(min_tuple) - 2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

a = 1
b = N

for i in range(1, N):
    if N % i == 0:
        j = N // i
        if (i + j) < (a + b):
            a = i
            b = j

print(a + b -2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ans = N**2
for i in range(1, N):
    if N % i == 0:
        j = N // i
        step = i + j - 2
        if N == i * j and step < ans:
            ans = step
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
x = int(input())
i = int(math.sqrt(x))
while (i < x):
    if (x%i == 0):
        print (int((x/i)+i)-2)
        break
    i += 1

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
answer = num-1

for x in range(2, num + 1):
    if num % x == 0:
        y = num / x
        a = x + y - 2
        if answer >= a:
            answer = a
        else:
            break
print(int(answer))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=[]
d=[]

for i in range(1,n+1):
  if n%i==0:
    s.append((i-1,n//i-1))

for i in s:
  d.append(i[0]+i[1])

print(min(d))

Submission status: Time Limit Exceeded

Solution code:

N=input()
N=int(N)
A=10**12
I=((N**(1/2))//1)

for a in range(1,round(I+1)):
    for b in range(a,(10**12)+1):
        if N==a*b:
            if a+b-2<A:
                A=a+b-2
            else:
                pass
        else:
            pass

print(A)

Submission status: Time Limit Exceeded

Solution code:

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

for a in range(1,(10**12)+1):
    for b in range(1,(10**12)+1):
        if N==a*b:
            if a+b-2<A:
                A=a+b-2
            else:
                pass
        else:
            pass

print(A)

Submission status: Time Limit Exceeded

Solution code:
ans = 10**12
n = int(input())
for a in range(1,n+1):
  for b in range(1,n+1):
    if a * b == n:
      ans_n = a + b -2
      if ans > ans_n:
        ans = ans_n
print(ans)

Submission status: Time Limit Exceeded

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

print(min)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 9999999999999
for i in range(1, n+1):
    x1 = i
    x2 = n // x1
    if x1 * x2 == n and x1 + x2 < ans:
        ans = x1-1 + x2 -1
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(1, 10**7+1):
    q, m = divmod(n, i)
    if m == 0:
        ans = min(ans, q+i)

print(ans-2)

Submission status: Time Limit Exceeded

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

for i in range(1, 10**8+1):
    q, m = divmod(n, i)
    if m == 0:
        ans = min(ans, q+i)

print(ans-2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

for i in range(1 , 10 ** 6 + 1):
  for j in range(1 , 10 ** 6 + 1):
    if i * j == N:
      I = i - 1
      J = j - 1
      break
      
print(I + J)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

for i in range(1 , 10 ** 6 + 1):
  for j in range(1 , 10 ** 6 + 1):
    if i * j == N:
      I = i - 1
      J = j - 1
      break
      
print(I * J)

Submission status: Time Limit Exceeded

Solution code:
input_num = int(input())

minimam = input_num
for i in range(1,input_num+1):
    q, mod = divmod(input_num, i)
    distance = q + i -2
    if mod == 0 and minimam > distance:
        minimam = distance
print(minimam)

Submission status: Time Limit Exceeded

Solution code:
import math 
 
n = int(input())
m = int(round(math.sqrt(n)))
while True:
    p, q = divmod(n, m)
    if q == 0:
        print(m + p - 2)
        break
    else:
        m += 1

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

            for j in range(cnt):
                arr.append(i)

    if temp!=1:
        arr.append(temp)

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

    return arr


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_list = factorization(N)
# print(prime_list)

ans = float('inf')

for p in itertools.product([0,1],repeat=len(prime_list)):
    # print(p)
    div = [1,1]
    for i in range(len(prime_list)):
        div[p[i]] *= prime_list[i]
    # print(div)

    if div[0] + div[1] - 2 < ans:
        ans = div[0] + div[1] - 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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_list = prime_factorize(N)
# print(prime_list)

ans = float('inf')

for p in itertools.product([0,1],repeat=len(prime_list)):
    # print(p)
    div = [1,1]
    for i in range(len(prime_list)):
        div[p[i]] *= prime_list[i]
    # print(div)

    if div[0] + div[1] - 2 < ans:
        ans = div[0] + div[1] - 2

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

divisor = []
for i in range(1 , N+1):
    if N % i == 0:
        divisor.append(i)

distance = []
for j in range(int(len(divisor))-1):
    M = (N / int(divisor[j])) + int(divisor[j])
    distance.append(M)

import math

if int(len(divisor)) == 2:
    print(N-1)
else:
    print(math.floor(min(distance))-2)

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
s=set()
l=[i for i in range(1,x)]

for i in reversed(l):
  if x%i == 0:
    a=i+x//i-2
    s.add(a)
    if min(s)-a <0:
      break
print(min(s))

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
i = 1
s=set()
while x/i>=1:
  if x%i == 0:
    s.add(i+x//i-2)
    a1=i+x//i-2
    a2=a1
    if a2-a1 >0:
      break
  i = i + 1
print(min(s))

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
i = 1
s=set()
while x/i>=1:
  if x%i == 0:
    s.add(i+x//i-2)
  i = i + 1
print(min(s))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
pre_i = -1
pre_j = -1
for i in range(1,n+1):
  if n%i == 0:
    j = int(n/i)
    if j == pre_i and i == pre_j:
      break
    pre_i = i
    pre_j = j
print (i+j-2)

Submission status: Time Limit Exceeded

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

ans_i = []
ans_j = []
for i in range(1, 1000001):
    for j in range(1, 1000001):
        if( i*j == N ):
            ans_i.append(i)
            ans_j.append(j)
        if( j > N ):
            break
    if( i > N ):
        break

path_i = N
path_j = N
while( len(ans_i)> 0 ):
    i = ans_i.pop()
    j = ans_j.pop()
    if( i+j < path_i+path_j ):
        path_i = i
        path_j = j
    
print( path_i+path_j-2 )

Submission status: Time Limit Exceeded

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

n = int(input())
a = []

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

print(min(a))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
b = input()
a = int(b)

c = int(math.sqrt(a))

for i in range(1000000000):
    d = a / (c + i)
    if d.is_integer() == True:
        break

e = d + c + i - 2
print(int(e))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

cand = []
for i in range(1, n):
  if n % i == 0:
    cand.append((i - 1) + (n // i - 1))
print(min(cand))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
k=list()
for i in range(int(n*0.5)):
  if n%(i+1)==0:
    k.append(int(i+n/(i+1)-1))
print(min(k))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
k=list()
for i in range(n):
  if n%(i+1)==0:
    k.append(int(i+n/(i+1)-1))
print(min(k))

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())

n = ii()

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


print(ans-2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
yakusuu_list = []
for i in range (1,N+1):
  if N % i == 0:
    yakusuu_list.append([i,N//i])
kyori_list =[]
for a in yakusuu_list:
  [i,j] = a
  kyori_list.append(i+j-2)
print(min(kyori_list))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

def pk(n):
  b = 2
  fct = []
  while b * b <= n:
    while n % b == 0:
      n //= b
      fct.append(b)
    b += 1
  if n > 1:
    fct.append(n)
  return fct

n = int(input())
temp = np.prod(pk(n))
sqi = int(math.sqrt(temp))
while 1:
  if temp % sqi != 0:
    sqi += 1
  else:
    break
i = sqi
j = temp // sqi
print(i + j -2)

Submission status: Time Limit Exceeded

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

print(data)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

class Kake:
    def __init__(self, n):
        self.n = n
        
    def div(self):
        div_dict = {}
        
        for i in range(1, int(self.n/2)+1):
            if self.n % i == 0 and i <= (self.n/i):
                div_dict[i] = int(self.n / i)

        sa_list = list()
        for i in div_dict:
            sa_list.append((i-1)+(div_dict[i]-1))
        print(min(sa_list))
        
kake = Kake(n)
kake.div()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
minn=N-1
for i in range(N-1):
    if N%(i+1)==0 and minn>N//(i+1)-1+i:
        minn=N//(i+1)-1+i
if minn<=(N-1):
    print(minn)
else:
    print(N-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
a = int(input())

x = 0
y = 0

ans = 1000000000000

for i in range(1,a):
	if a % i == 0:
		x = int(a / i)
		if ans > ((x - 1) + (i - 1)):
			ans = (x - 1) + (i - 1)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

lst = []
for i in range(1, N + 1):
	if N % i == 0 and i <= N // i:
		row = i
		column = N // i
		move = row - 1 + column - 1
		lst.append(move)
print(min(lst))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

lst = []

for i in range(1, N + 1):
	if N % i == 0:
		row = i
		column = N // i
		move = i - 1 + N // i -1
		lst.append(move)
print(min(lst))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

print(a+b-2)

Submission status: Time Limit Exceeded

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

def get_score(i, j):
    return i+j-2

n = int(input())
prime_list = prime_factorize(n)
# print(prime_list)

ans = 1e13
for i in range(2 ** len(prime_list)):
    total = 0
    a = 1
    b = 1
    for j in range(len(prime_list)):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            a *= prime_list[j]
        else:
            b *= prime_list[j]
    score = get_score(a, b)
    if ans > score:
        ans = score
print(ans)

Submission status: Time Limit Exceeded

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

num = int(input())
yaku = make_divisors(num)
ans = float("inf")
for i in yaku:
    for j in yaku:
        if i*j==num:
            ans=min(ans,i+j-2)
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(1,N):
    if N % i == 0:
        if n > i + N / i:
            n = i + N / i

if n < N:
    print(int(n-2))
else:
    print(int(n-1))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
result=1000000000000
for i in range(n):
  nn=n/(i+1)
  if (nn.is_integer() and result>nn+i-1):
    result=nn+i-1
print(int(result))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import itertools
def solve():
    N = int(input())
    primes = itertools.permutations(prime_factorize(N))

    min_sub = float('inf')
    for p in primes:
        p = [1] + list(p) + [1]
        for border in range(1, len(p)):
            a = reduce(lambda x, y: x*y, p[:border])
            b = reduce(lambda x, y: x*y, p[border:])
        
            if min_sub > a + b:
                min_sub = a + b 
    
    print(min_sub-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                

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

q=list()

for i in range(1,n):
  if n%i==0:
    q.append(i+n/i)
    
  else:
    pass
  
q.sort()
print(round(q[0]-2))

Submission status: Time Limit Exceeded

Solution code:
import math

if __name__ == '__main__':
    n = int(input())
    N = math.ceil(math.sqrt(n))
    k = n+1
    for i in range(n):
        if n % N == 0:
            print(int(n/N - 1) + N - 1)
            break
        else:
            N = N + 1

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

li=[]
l=0
m=0

for i in range(N//2):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
  else:
    pass

print(int(min(li)))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

li=[]
l=0
m=0

for i in range(-(-N//2)):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
  else:
    pass

print(int(min(li)))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

li=[]
l=0
m=0

for i in range(N//2+1):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
  else:
    pass

print(int(min(li)))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

li=[]
l=0
m=0

for i in range(N):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
  else:
    pass

print(int(min(li)))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

li=[]
l=0
m=0

for i in range(N):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
    l=0
    m=0
  else:
    pass

print(int(min(li)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

i=1
List=[]
while i<n+1:
    if n/i==n//i:
        List.append(n//i)
    i=i+1
a=len(List)
print(List[a//2]+List[a//2-1]-2)

Submission status: Time Limit Exceeded

Solution code:
import math

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

def main(argv):
    n = int(input())
    l = (None,)
    """
    i = n + 1
    while(True):
        i -= 1
        if(i <= 0):
            break
        elif(n % i == 0):
            l = (i, n / i)
        if(i < n / i):
            break
    print(int(l[0] + l[1] - 2))
    """
    """
    for i in range(n + 1, 1, -1):
        if(n % i == 0):
            l = (i, n / i)
        if(i < n / i):
            break
    """
    if n == 2:print(1);exit()
    elif n == 3:print(2);exit()
    for i in range(int(math.sqrt(n)) - 1, n, 1):
        if(n % i == 0):
            l = (i, n / i)
            break
    print(int(l[0] + l[1] - 2))

if __name__ == "__main__": main(sys.argv)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

sn = math.sqrt(N) // 1

while True:
  if N % sn == 0:
    break
  sn += 1

print(int(sn + (N / sn) - 2))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = (None,)
i = n + 1
while(True):
    i -= 1
    if(i <= 0):
        break
    elif(n % i == 0):
        l = (i, n / i)
    if(i < n / i):
        break
print(int(l[0] + l[1] - 2))

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
c=0
t=True
i=math.ceil(math.sqrt(N)/2)
while t:
  j=i
  while j>0:
    if i*j==N:
      c=i+j-2
      t=False
      break
    j-=1
  i+=1
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
 
mi = 10**10
 
for a in range(int(math.sqrt(N)), N+1, 1):
  if N % a == 0:
    b = N//a
    if mi > a+b-2:
      mi = a+b-2
print(mi)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input());
s = n - 1
for i in range(1,n):
    t = n / i
    if t.is_integer() == True and s > (t-1)+(i-1):
        s = (t-1)+(i-1)
print(int(s))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


def factorize(n):
    f = []
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        while tmp % i == 0:
            f.append(i)
            tmp //= i
    if tmp != 1:
        f.append(tmp)
    if not f:
        f.append(n)
    return f


def distance(s):
    a, b = 1, 1
    for i, si in enumerate(s):
        if si == "0":
            a *= factors[i]
        else:
            b *= factors[i]
    return a + b - 2


@lru_cache()
def kp(i, s):
    if i == 0:
        return 0, s
    else:
        if distance("0" + s) < distance("1" + s):
            return kp(i - 1, "0" + s)
        else:
            return kp(i - 1, "1" + s)


def sa(f):
    d = 999999999999
    for i in range(2 ** len(f)):
        d = min(d, distance("{}{}".format("0" * (len(f) - 1), bin(i)[2:])[-len(f):]))
    return d


N = int(input())
factors = factorize(N)
print(sa(factors))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
nums = 0
for i in range(N):
  if i > np.sqrt(N):
    break
  elif N % (i+1) == 0:
    nums = i + N // (i+1) - 1
print(nums)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

# print(N)

ans = N
i = 1
while i < N:
    # print(i)
    
    div, mod = divmod(N, i)
    
    if mod == 0:
        # print(i)
        # print(div)
        # print(mod)
        
        ans = min(ans, ((i - 1) + (div - 1)))
    
    i += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def work_through(): 
  i, j = 1, 1
  cnt = 0

  arr = []
  arr.append([i, j])

  n = int(input())

  while True:
    tmp = []
    length = len(arr)
    for i in range(0, length):
      x, y = arr.pop()
      if x * y == n:
        return cnt
      tmp.append([x + 1, y])
      tmp.append([x, y + 1])
    arr = tmp
    cnt += 1

print(work_through())

Submission status: Time Limit Exceeded

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

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

d = prime_factorize(N)

ans = 2**64

A = d

for i in range(1 << len(A)):
    a = []
    b = []
    ao = 1
    bo = 1
    for j in range(len(A)):
        if ((i >> j) & 1) == 1:
            a.append(A[j])
        else:
            b.append(A[j])
            
    for j in range(len(a)):
        ao *= a[j]
    for j in range(len(b)):
        bo *= b[j]
        
    ans = min(ans, ao+bo-2)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:


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

    # divisors.sort()
    return divisors


N = int(input())
a = make_divisors(N)
b = []
c = []

for j in range(len(a)):
    for k in range(len(a)):
        if a[j] * a[k] == N:
            b.append([a[j],a[k]])

for l in range(len(b)):
    c.append(b[l][0] + b[l][1])

print(min(c) - 2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = N
for i in range(1, N+1):
    for j in range(1, N+1):
        if N == i * j:
            flag = i + j - 2

            if flag <= s:
                s = flag

print(s)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n = int(input())

list_p = []
for i in range(1, n):

    j = n / i

    if j.is_integer():
        list_p.append([i, j, i+j])
list_sorted = sorted(list_p, key=itemgetter(2))
print(int(list_sorted[0][0] + list_sorted[0][1] - 2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
MIN = n
x = 1
while np.sqrt(n) >= x:
    if n % x == 0:
        MIN = min([MIN,x + n/x - 2])
    x += 1
print(int(MIN))

Submission status: Time Limit Exceeded

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

#input
N = int(input())

#output
minimum = 0
ans = N-1
for i in range(1, N+1):
    if float.is_integer(N/i):
        a = i
        b = int(N/i)
        c = a+b-2
        ans = min(c, ans)
        
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())


def main():

    factorized = factorizer(N)

    if factorized.get(N) is not None:
        print(N - 1)
        quit()

    end = N ** 0.5
    minv = 10000000000
    for i in range(1, int(end)):
        for j in range(i, N):
            # print("i:{0}  j:{1}  i*j:{2}  N:{3}".format(i, j, i * j, N))
            if (i * j) == N:
                minv = min(minv, i + j - 2)

    print(minv)


def factorizer(n):
    """
    素因数分解するということは、
    2 ~ Nまでの数で割り続けるということ　試し割り
    割れなくなったら次の数で割る。
    素数を除いて、素因数の最大値は√nなので、それを超えたらやめる
    """
    res = {1: 1}  # １は必ずある
    calcEnd = n ** 0.5

    for i in range(2, int(calcEnd) + 2, 1):
        while n % i == 0:
            if res.get(i) is None:
                res[i] = 1
            else:
                res[i] += 1
            n /= i
            # print("n:{0}".format(n))

    # GCDが素数だった時の処理
    if n > 1:
        res[int(n)] = 1

    # print("res is {}".format(res))
    return res


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
i=1
while(True):
    if i**2>=N:
        break
    i+=1
while(True):
    if N%i==0:
        S=i+N//i-2
        print(S)
        break
    i+=1