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

n = int(input())

start = int(math.sqrt(n)+0.5)

for i in range(start ,n+1):
    if n % i == 0:
        a = i
        b = n // i
        break

print(a + b -2)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())

start = math.ceil(n**0.5)

for i in range(start ,n+1):
    if n % i == 0:
        a = i
        b = n // i
        break

print(a + b -2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(1,n):
  a = n / i
  if n % i == 0:
    l.append(int(i + a - 2))
  if all([n%i for i in range(2,int(n**.5)+1)]):
    break
print(min(l))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

while n != 1:
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            prime.append(i)
            n /= i
            break
    else:
        prime.append(int(n))
        n = 1

for bit in range(1 << len(prime)):
    a = 1
    b = 1

    for i in range(len(prime)):
        if bit >> i & 1:
            a *= prime[i]
        else:
            b *= prime[i]

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime_number(x):
    if x==2 or x==3:
        return True
    else:
        if x%2==0 or x%3==0:
            return False
        else:
            divisor_lst = [1,x]
            for i in range(1,x+1):
                if i%2!=0 and i%3!=0:
                    if i not in divisor_lst and x%i==0:
                        return False
                        break
            else:
                return True

n = int(input())

if prime_number(n):
    print(n-1)
else:
    i = 1
    j = n//i
    divisor_lst = []
    while i<=j:
        i += 1
        j = n//i
        if n%i==0:
            divisor_lst.append([i,j])

    n_x = divisor_lst[-1][0]
    n_y = divisor_lst[-1][1]
    print(n_x+n_y-2)

Submission status: Time Limit Exceeded

Solution code:
def prime_number(x):
    if x==2 or x==3:
        return True
    else:
        if x%2==0 or x%3==0:
            return False
        else:
            divisor_lst = [1,x]
            for i in range(1,x+1):
                if i not in divisor_lst and x%i==0:
                    return False
                    break
            else:
                return True

n = int(input())

if prime_number(n):
    print(n-1)
else:
    i = 1
    j = n//i
    divisor_lst = []
    while i<=j:
        i += 1
        j = n//i
        if n%i==0:
            divisor_lst.append([i,j])

    n_x = divisor_lst[-1][0]
    n_y = divisor_lst[-1][1]
    print(n_x+n_y-2)

Submission status: Time Limit Exceeded

Solution code:
def prime_number(x):
    if x==2 or x==3:
        return True
    else:
        if x%2==0 or x%3==0:
            return False
        else:
            divisor_lst = [1,x]
            for i in range(1,x+1):
                if i not in divisor_lst and x%i==0:
                    return False
                    break
            else:
                return True

n = int(input())

if prime_number(n):
    print(n-1)
else:
    i = 1
    divisor_lst = []
    while True:
        i += 1
        j = n//i
        if n%i==0:
            divisor_lst.append([i,j])
        if i>j:
            break

    n_x = divisor_lst[-1][0]
    n_y = divisor_lst[-1][1]
    print(n_x+n_y-2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

a = pow(10,12)

is_not_prime = False
for k in range(2, int(math.sqrt(N)) + 1):
    if N % k == 0:
        is_not_prime = True
        break
if is_not_prime:
    for i in range(1, int(N*0.5)):

        j = N/i
        if j.is_integer():

            if (i+int(j)) < a:
                a = i+int(j)
        if j < 2:
            break

    print(a - 2)
else:
    print(N - 1)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

a = pow(10,12)

is_not_prime = False
for k in range(2, int(math.sqrt(N)) + 1):
    if N % k == 0:
        is_not_prime = True
        break
if is_not_prime:
    for i in range(1, int(N*0.5)):

        j = N/i
        if j.is_integer():

            if (i+int(j)) < a:
                a = i+int(j)
        if j < 1:
            break

    print(a - 2)
else:
    print(N - 1)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

a = pow(10,12)

is_not_prime = False
for k in range(2, int(math.sqrt(N)) + 1):
    if N % k == 0:
        is_not_prime = True
        break
if is_not_prime:
    for i in range(1, N):

        j = N/i
        if j.is_integer():

            if (i+int(j)) < a:
                a = i+int(j)
        if j < 1:
            break

    print(a - 2)
else:
    print(N - 1)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

a = pow(10,12)

is_not_prime = False
for k in range(2, int(math.sqrt(N)) + 1):
    if N % k == 0:
        is_not_prime = True
        break
if is_not_prime:
    for i in range(1, N):

        j = N/i
        if j.is_integer():

            if (i+int(j)) < a:
                a = i+int(j)

    print(a - 2)
else:
    print(N - 1)

Submission status: Time Limit Exceeded

Solution code:
import math


def isprime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0: return False
    return True


def ij(N):
    i = 1
    sv_i = 0
    sv_j = 0
    sv_x = 10**12
    while True:
        if n % i == 0:
            x = i + n / i

            if x < sv_x:
                sv_x = int(x)
                sv_i = int(i)
                sv_j = int(n / i)

        i += 1
        if i >= n or isprime(N) == True:
            break
    return ((sv_i - 1) + (sv_j - 1))


n = int(input())
print(ij(n))

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
stack = queue.Queue()
stack.put([1,1,0])
count = 0
while True:
    point = stack.get()
    point0,point1,point2 = point[0],point[1],point[2]+1
    point_x = [point0+1,point1,point2]
    point_y = [point0,point1+1,point2]
    if point_x[0] * point_x[1] == N:
        print(point_x[2])
        break
    if point_y[0] * point_y[1] == N:
        print(point_y[2])
        break
    stack.put(point_x)
    stack.put(point_y)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())

ans = []

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

def mul(l):
    result = 1
    for i in l:
        result *= i
    return result

n = int(input())

prime_list = primes(n)

i,j = 1,n
for m in range(len(prime_list)//2 + 1):
    cmb = set(itertools.combinations(prime_list, m))
    for c in cmb:
        s = mul(c)
        t = n//s
        if abs(s-t) < abs(i-j):
            i,j = s,t

print(i+j-2)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

def mul(l):
    result = 1
    for i in l:
        result *= i
    return result

n = int(input())

prime_list = primes(n)

i,j = 1,n
for m in range(len(prime_list)):
    cmb = set(itertools.combinations(prime_list, m))
    for c in cmb:
        s = mul(c)
        t = n//s
        if abs(s-t) < abs(i-j):
            i,j = s,t

print(i+j-2)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

def mul(l):
    result = 1
    for i in l:
        result *= i
    return result

n = int(input())

prime_list = primes(n)

i,j = 1,n
for m in range(len(prime_list)):
    cmb = list(set(itertools.combinations(primes(n), m)))
    for c in cmb:
        s = mul(c)
        t = n//s
        if abs(s-t) < abs(i-j):
            i,j = s,t

print(i+j-2)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def primes(n):
    l = []
    i = 2
    while i <= n**(1/2):
        while n % i == 0:
            n //= i
            l.append(i)
        i += 1
    l.append(n)
    return l

def mul(l):
    result = 1
    for i in l:
        result *= i
    return result

n = int(input())

per = list(set(itertools.permutations(primes(n))))

i,j = 1,n
for p in per:
    for k in range(len(p)):
        s,t = mul(p[:k]), mul(p[k:])
        if abs(s-t) < abs(i-j):
            i,j = s,t

print(i+j-2)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def primes(n):
    l = []
    i = 2
    while i <= n**(1/2):
        while n % i == 0:
            n //= i
            l.append(i)
        i += 1
    l.append(n)
    return l

def mul(l):
    result = 1
    for i in l:
        result *= i
    return result

n = int(input())

per = list(itertools.permutations(primes(n)))

i,j = 1,n
for p in per:
    for k in range(len(p)):
        s,t = mul(p[:k]), mul(p[k:])
        if abs(s-t) < abs(i-j):
            i,j = s,t

print(i+j-2)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
bar=10**12

def f(x):
  d=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      d.append(i)
      if i!=x//i:
        d.append(x//i)
  d.sort()
  return d

for i in f(N):
  for j in f(N):
    if i*j==N and i+j<bar:
      bar=i+j
      x=i
      y=j

print(x-1+y-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import itertools

N = int(input())
prime_factor = []
for i in range(2,int(math.sqrt(N))+1):
  while N%i == 0:
    prime_factor.append(i)
    N/=i
    
if N > 1:
  prime_factor.append(N)
  prime_factor.append(1)

  
prime_factor = np.array(prime_factor)
prime_len = len(prime_factor) // 2
comb = set(range(0,len(prime_factor)))

min_root = -1

for i in range(1,(prime_len+1)):
  for sets in itertools.combinations(list(comb),i):
    sets = set(sets)
    sets_c = comb - sets
    min_cand = prime_factor[list(sets)].prod() + prime_factor[list(sets_c)].prod()
    if min_cand < min_root or min_root < 0:
      min_root = min_cand
      
print(int(min_root - 2))

Submission status: Time Limit Exceeded

Solution code:
def solve():
  n = int(input())
  act = 1
  result = 0
  
  while True:
    _max = act ** 2
    if act <= _max:
      _act = 1
      
      while act * _act < _max:
        _act += 1
        
        if _act * act == n:
          return act + _act - 2
    
    act += 1

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
ans=1000000000000
N=int(input())
for i in range(1,N+1):
    if (N%i==0):
        j=N//i
        move=(i-1)+(j-1)
        ans=min(ans,move)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
n = 2
kake = 1
flag = 0
while flag == 0:
    if n * kake == N:
        flag = 1
        break
    if n < kake:
        n += 1
        kake = 1
        continue
    kake += 1
ans = (n - 1) + (kake - 1)
print(ans)

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)
    divisors.sort()
  return divisors
l = make_divisors(N)
if len(l) % 2 == 0:
  x = l[len(l) // 2 - 1]
  y = l[len(l) // 2]
  print(x + y - 2)
else:
  x = l[len(l) // 2]
  print(2 * (x-1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = n** 0.5
if n%a == 0:
    print(int(2*a)-2)
else:
    while n%a != 0:
        a = a//1+1 
        if n%a == 0:
            print(int(a + n//a-2))
            exit()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from itertools import combinations

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())
factor = [1] + prime_factorize(n)

ans = int(1e13)
for i in range(1, len(factor)//2 + 1):
    for c in combinations(factor, i):
        a = reduce(lambda x,y:x*y, c)
        b = n // a
        ans = min(ans, a + b - 2)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools


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

    return N,


def solve(N, ):
    move = 1000000000000
    for i in range(N//2):
        a = i + 1
        if N % a != 0:
            continue
        b = N // a
        move = min(move, a + b - 2)
    return move


if __name__ == '__main__':
    input = read()
    print(solve(*input))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

def main():
    N = int(input())
    lp = prime_factorize(N)
    ans = N - 1
    #print(lp)
    for j in range(len(lp)//2):
        l = list(itertools.combinations(lp,j+1))
        la = list(set(l))
        la = list(map(np.prod, la))
        #print(la)
        for i in range(len(la)):
            #print(l[i])
            a = la[i]
            b = N // a                
            #print(a, b)
            if (a != 1) and (b != 1):
                buf = a + b - 2
            else:
                buf = a + b - 1
            if ans > buf:
                ans = buf
    print(ans)

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__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

def main():
    N = int(input())
    lp = prime_factorize(N)
    ans = N - 1
    #print(lp)
    for j in range(len(lp)//2):
        l = list(itertools.combinations(lp,j+1))
        l = list(set(l))
        for i in range(len(l)):
            #print(l[i])
            a = np.prod(l[i])
            b = N // a                
            #print(a, b)
            if (a != 1) and (b != 1):
                buf = a + b - 2
            else:
                buf = a + b - 1
            if ans > buf:
                ans = buf
    print(ans)

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__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

def main():
    N = int(input())
    lp = prime_factorize(N)
    ans = N - 1
    #print(lp)
    for j in range(len(lp)//2):
        l = list(itertools.combinations(lp,j+1))
        for i in range(len(l)):
            #print(l[i])
            a = np.prod(l[i])
            b = N // a                
            #print(a, b)
            if (a != 1) and (b != 1):
                buf = a + b - 2
            else:
                buf = a + b - 1
            if ans > buf:
                ans = buf
    print(ans)

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__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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
            arr.append([i, cnt])

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

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

    return arr

def comb(array):
  min_prod = 10 ** 12 + 1
  for i in itertools.permutations(array):
    for j in range(len(i)):
      prod = np.prod(i[:j]) + np.prod(i[j:])
      if prod < min_prod:
        min_prod = prod

  return int(min_prod)


n = int(input())

fs = factorization(n)

flat_f = [1]
for f in fs:
  for i in range(f[1]):
    flat_f.append(f[0])

print(comb(flat_f) - 2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve():
    N = int(input())
    
    r = 1e12
    for i in range(N - 1, int(np.sqrt(N)) - 1, -1):
        if N % i == 0:
            r = min(r, (N / i - 1) + (i - 1))
            
    
    print(int(r))

solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    
    r = 1e12
    for i in range(N - 1, 0, -1):
        if N % i == 0:
            r = min(r, (N / i - 1) + (i - 1))
            
    
    print(int(r))

solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

l1 = 0
for i in range(n // 2):
  if n % (i +1) == 0 and l1 == 0:
    l1 = (n // (i + 1) + i - 1)
  elif n % (i +1) == 0 and (n // (i + 1) + i - 1) < l1:
    l1 = (n // (i + 1) + i - 1)
print(l1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

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



    for a in reversed(range(1, int(math.sqrt(N))+1)):
        b = a
        while True:
            if a * b == N:
                print(a + b - 2)
                sys.exit()

            if a * b > N:
                break

            b += 1

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

l1 = []
for i in range(n // 2):
  q, mod = divmod(n , i + 1)
  if mod == 0:
    l1.append(q + i -1)
print(min(l1))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
#2<=N<10**12
a=1
b=1
count=[]
##N=a*b
#output=a+b-2
#積なので対称性よりa<=bとしてオッケー
for i in range(1,N+1):
    if N%i==0:
        a=i
        b=N/i
        if a<=b:
            count.append(int(a+b-2))
print(min(count))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mx=10**15
for i in range(1,n//2+1):
    if n%i==0 and n//i+i-2<mx:
        mx=n//i+i-2
print(mx)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  n=I()
  a=getPrimeList(n)

  ans=inf
  b=len(a)
  for i in range(2**b//2):
    _a=_b=1
    for j,x in enumerate(a):
      if ((i>>j)&1):
        _a*=x
      else:
        _b*=x
    ans=min(ans,_a+_b-2)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

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

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)
    return divisors
s=int(input())
x=make_divisors(s)
m=[]
for a in x:
    for b in x:
        if a*b==s and a<=b:
            k=a+b
            a=k-b
            m.append(k)
print(min(m)-2)

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
s=int(input())
x=make_divisors(s)
m=[]
for a in x:
    for b in x:
        if a*b==s and a<=b:
            k=a+b
            a=k-b
            m.append(k)
print(min(m)-2)

Submission status: Time Limit Exceeded

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

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

factor.sort()
print(factor[0])

Submission status: Time Limit Exceeded

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

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

print(min(factor))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

t = n - 1

for i in range(1,n+1):
    if n % i == 0:
        j = n / i
        if t > i + j:
            t = i + j -2

print(int(t))

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
c=[]
for i in range(math.ceil((4*N)**(1/2)-2), N):
    for k in range(1, i+1):
        if (1+k)*(i+1-k)==N:
            c.append(i)
print(min(c))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x=[]
for i in range(1,N+1):
    for j in range (i,N+1):
        if i*j==N:
            y=i+j
            x.append(y)
z=min(x)
print(z-2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

import itertools, copy

def powerset(L):
  pset = set()
  for n in range(len(L) + 1):
    for sset in itertools.combinations(L, n):
      pset.add(sset)
  return pset
    
def list_diff(first, second):
        first = copy.copy(first)
        for s in second:
            first.remove(s)
        return first

def prod(lst):
    ret = 1
    for a in lst:
        ret *= a
    return ret

def main():
    N = int(input())
    facs = factors(N)
    st = powerset(facs)

    mn_ij = 10**12
    for i in st:
        i = list(i)
        j = list_diff(facs, i)
        i, j = prod(i), prod(j)

        mn_ij = min(mn_ij, i+j)

    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

import itertools
import numpy as np

def powerset(L):
  pset = set()
  for n in range(len(L) + 1):
    for sset in itertools.combinations(L, n):
      pset.add(sset)
  return pset
    
def list_diff(first, second):
        first = first.copy()
        for s in second:
            first.remove(s)
        return first

def main():
    N = int(input())
    facs = factors(N)
    st = powerset(facs)

    mn_ij = 10**12
    for i in st:
        i = list(i)
        j = list_diff(facs, i)
        i, j = np.prod(i), np.prod(j)

        mn_ij = min(mn_ij, i+j)

    print(int(mn_ij-2))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x = N
y = N
ansx = N
ansy = N

for i in range(x+1):
    if i+1 > N:
        break
    for j in range(y+1):
        if j+1 > x+1:
            break
        if i*j == N:
            if ansx + ansy >i+j:
                ansx,ansy = i,j

print(ansx-1 + ansy -1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
X = []
for i in range(2,int(10**12+1)):
  q,mod = divmod(n,i)
  if mod == 0:
    s = i+q
    X.append(s)
  
print(min(X))

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
x,y=0,0
xy = 10**12
for i in range(1,a+1):
    if(a%i==0):
        x = i - 1
        y = int(a/i) - 1
        if x+y<xy:
            xy = x+y
print(xy)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
def divisor(num):
    L = []
    K = 0
    v = 0
    for i in range(num):
        if num%(i+1) == 0:
            L.append(i+1)
            K += 1
        else:
            continue
    if K%2 == 0:
        v = L[int(K/2)] + L[int(K/2-1)]
    elif K%2 == 1:
        v = 2*L[K/2]
    return v
print(divisor(N)-2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(1,n+1):
    for j in range(i,n+1):
        if(i*j>n):
            break
        elif(n==i*j):
            save=i-1+j-1
            list.append(save)
            
ans=min(list)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
list = []
min = 0
for i in range(1,num+1):
    p = num/i
    if p.is_integer() == True:
        if list.count(i) == 0 and list.count(int(p)) == 0:
            list.append(i)
            list.append(int(p))
        else:
          break
    

l = len(list)
list.sort()
if l%2 == 1:
    min = list[int((l/2))]*2-2
else:
    min = list[int(l/2)-1]+list[int(l/2)]-2
print(min)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
list = []
min = 0
for i in range(1,num+1):
    p = num/i
    if p.is_integer() == True:
        if list.count(i) == 0 and list.count(int(p)) == 0:
            list.append(i)
            list.append(int(p))
    

l = len(list)
list.sort()
if l%2 == 1:
    min = list[int((l/2))]*2-2
else:
    min = list[int(l/2)-1]+list[int(l/2)]-2
print(min)