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:

from functools import reduce
from operator import mul

def prod(arr):
    return reduce(mul, arr, 1)

def fancy(arr, index):
    output = []
    for i, v in enumerate(index):
        if v:
            output.append(arr[i])
    return output

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

N = int(input())
factors = prime_factorize(N)
selectors = [list(map(bool, map(int, list("{0:b}".format(i).zfill(len(factors)))))) for i in range(1, 2**len(factors))]
combinations = [(prod(fancy(factors, selector)), N//prod(fancy(factors, selector))) for selector in selectors]
distances = [combination[0]-1 + combination[1]-1 for combination in combinations]
print(min(distances))

Submission status: Time Limit Exceeded

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

move = N
for i in range(2,N+1):
    if N % i == 0:
        j = N / i
        if move > int(i+j-2):
            move = int(i+j-2)

print(move)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain,combinations


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

def _powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1, 0, -1))


def prod(iterable):
    ret = 1
    for i in iterable:
        ret *= i
    return ret


div_list = prime_factorize(N)
if(div_list) == 1:
    ans = sum(div_list) - 1
else:
    ans = N - 1
    power_set = _powerset(div_list)
    for p in power_set:
        left = prod(p)
        right = N // left
        ans = min(ans, left + right -2)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import math

def main(N):
    min_dis = None
    for i in range(1, int(N/2+1)):
        if N % i == 0 and N % i <= 9:
            j = int(N / i)
            n_dis = i + j - 2
            if min_dis is None or n_dis < min_dis:
                min_dis = n_dis
    if not min_dis:
        return 0
    return min_dis


if __name__ == "__main__":
    N = int(input())
    my_ans = main(N)
    print(my_ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct
A = factorize(N)
if len(A) == 1:
    ans = N-1
else: 
    ans = 9999999999999999999999
    from itertools import permutations as P
    from functools import reduce
    for i in range(1,len(A)):
        l1 = list(P(A,i))
        for l1_temp in l1:
            l2 = list(filter(lambda x : x not in l1,A))
            ans_1 = reduce(lambda x,y:x * y,l1_temp)
            ans_2 = N//ans_1
            ans_temp = (ans_1 + ans_2 -2)
            ans = min(ans,ans_temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
for i in range(2,1000000000001):
    for j in range(1,1000000000001):
        if n == i * j:
            if i != 1 and j != 1:
                if i >= j:
                    print(i)
                else:
                    print(j)
            elif i == 1 or j == 1:
                if i > j:
                    print(i)
                else:
                    print(j)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
for i in range(a):
	p=a//(i+1)
	if (i+1)>=p and a%(i+1)==0:
		break
print(i+p-1)

Submission status: Time Limit Exceeded

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

def isPrime(n) : 
  
    # Corner cases 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
  
    # This is checked so that we can skip  
    # middle five numbers in below loop 
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True




if isPrime(N):
  print(N - 1)
else:
  x = math.floor(N**(0.5))
  for i in range(x,N+1):
    a = N/i
    if (a%1 == 0):
      print(int(a) + i -2)
      break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = 10**12

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

min_total = 100000000000000
for a in range(1, N // 2 + 2):
    b = N / a
    if b.is_integer():
        tmp_a_and_b = a + b
        if tmp_a_and_b < min_total:
            min_total = tmp_a_and_b

print(int(min_total - 2))

Submission status: Time Limit Exceeded

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

print(m-2)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import math

def main(N):
    min_dis = None
    for i in range(1, int(N)):
        if N % i == 0 and N % i <= 9:
            j = int(N / i)
            n_dis = i + j - 2
            if min_dis is None or n_dis < min_dis:
                min_dis = n_dis
    return min_dis


if __name__ == "__main__":
    N = int(input())
    my_ans = main(N)
    print(my_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())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  if d[i]**2==n:
    a.append([d[i], d[i]])
    break
  for j in range(i+1, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
factor = []
tmp = n
for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
if tmp != 1:
    factor.append(tmp)
w = len(factor)
if w == 0:
    factor.append(n)
    w = 1
if w == 1:
    print(n - 1)
else:
    # bit = [0] * w
    ans = 1000000000000
    for i in range(1, 2 ** w):
        a, b = 1, 1
        for j in range(w):
            # bit[j] = i & (2 ** j)
            if i & (2 ** j) == 0:
                a *= factor[j]
            else:
                b *= factor[j]
        if a + b - 2 < ans:
            ans = a + b - 2
        # print(i, bit, a, b, ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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())

cnt = 0
i = 2
a = prime_factorize(n)
if len(a) == 1:
    a.append(1)
b = []
for i in range(1,len(a) // 2 + 2):
    b.append(list(itertools.combinations(a, i)))

m1 = 10**12
m2 = 10**12
for i in range(len(b)):
    for j in range(len(b[i])):
        c = np.prod(b[i][j])
        d = n // c
        if m1+m2 > c+d:
            m1 = c
            m2 = d

print(m1+m2-2)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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())

cnt = 0
i = 2
a = prime_factorize(n)
if len(a) == 1:
    a.append(1)
b = []
for i in range(1,len(a)+1):
    b.append(list(itertools.combinations(a, i)))

m1 = 10**12
m2 = 10**12
for i in range(len(b)):
    for j in range(len(b[i])):
        c = np.prod(b[i][j])
        d = n // c
        if m1+m2 > c+d:
            m1 = c
            m2 = d

print(m1+m2-2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
i = 1
j = 1
a = 0
change_dir = 0
while n != (i * j):
    if change_dir == 0:
        i = i + 1
        change_dir = 1
        a = a + 1
    else:
        j = j + 1
        change_dir = 0
        a = a + 1
else:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
y=int(a ** (1/2))
z=y
while y*z != a:
 if y*z > a:
  z=z-1
 if y*z < a:
  y=y+1
print(y+z-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

N = int(input())
facts = prime_factorize(N)
ans = float('inf')
for i in range(2**len(facts)):
  x1 = 1
  for idx1, flag in enumerate(bin(i)[2:]):
    if flag == '0':
      x1 *= facts[idx1]
  ans = min(ans, x1+N//x1-2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
i=2
j=1
flag=0
x=0
y=0
min=a**0.5
intmin=int(min)

for i in range(intmin,a):
    if a%i == 0:
        if i!=a:
            print(int(i-2+(a/i)))
        else:
            print(a-1)
        break


# try:
#     for i in range(2,a//2):
#         mod=a%i
#         if mod==0:
#             if min > (a/i) + i -2:
#                 min = (a/i) + i -2
#     print(min)
# except ZeroDivisionError:
#     print("ZeroDivisionError!!")

Submission status: Time Limit Exceeded

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

def isPrime(n) : 
  
    # Corner cases 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
  
    # This is checked so that we can skip  
    # middle five numbers in below loop 
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True




if isPrime(N):
  print(N - 1)
else:
  x = math.floor(N**(0.5))
  for i in range(x,N+1):
    if N%i == 0:
      print(N//i + i -2)
      break

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.extend([b]*e)
        b, e = b + 1, 0
    if n > 1:
        fct.extend([n]*1)
    return fct

N = int(input())
arr = factorize(N)
M = len(arr)
ans = N
for i in range(2**(M-1)):
    A = 1
    B = 1
    for j in range(M):
        if (i>>j)&1:
            A *= arr[j]
    B = N//A
    A = max(A-1,0)
    B = max(B-1,0)
    ans = min(ans,A+B)

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())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  if d[i]**2==n:
    a.append([d[i], d[i]])
    continue
  for j in range(i+1, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
factor = []
tmp = n
for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
if tmp != 1:
    factor.append(tmp)
if len(factor) == 0:
    factor.append(n)
if len(factor) == 1:
    print(factor[0] - 1)
else:
    ans = float("inf")
    for i in range(1, 2 ** len(factor)):
        a, b = 1, 1
        for j in range(len(factor)):
            if i & (2 ** j) == 0:
                a *= factor[j]
            else:
                b *= factor[j]
        if a + b - 2 < ans:
            ans = a + b - 2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
p=1+N
for i in range(1,N):
    if N%i==0:
        if (N/i)+i<=p:
            p=(N//i)+i
        else:
            p=p
    else:
        pass

print(p-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

N = int(input())
facts = prime_factorize(N)
ans = float('inf')
for i in range(2**len(facts)):
  x1 = 1
  for idx1, flag in enumerate(bin(i)[2:]):
    if flag == '0':
      x1 *= facts[idx1]
  ans = min(ans, x1+N//x1-2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
factor = []
tmp = n
for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
if tmp != 1:
    factor.append(tmp)
if len(factor) == 0:
    factor.append(n)
if len(factor) == 1:
    print(factor[0] - 1)
else:
    ans = float("inf")
    for i in range(1, 2 ** len(factor)):
        a, b = 1, 1
        for j in range(len(factor)):
            if i & (2 ** j) == 0:
                a *= factor[j]
            else:
                b *= factor[j]
        if a + b - 2 < ans:
            ans = a + b - 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())

cnt = 0
i = 2
a = prime_factorize(n)
if len(a) == 1:
    a.append(1)
b = []
for i in range(1,len(a)+1):
    b.append(list(itertools.combinations(a, i)))


m1 = 10**12
m2 = 10**12
for i in range(len(b)):
    for j in range(len(b[i])):
        c = 1
        d = 1
        for k in range(len(b[i][j])):
            c *= b[i][j][k]
        d = n // c
        if m1+m2 > c+d:
            m1 = c
            m2 = d

print(m1+m2-2)

Submission status: Time Limit Exceeded

Solution code:
import statistics
import sys

a = int(input())
num = []
for i in range(a):
    if a % (i+1) == 0:
        num.append(i+1)

if isinstance(statistics.median(num), int):
    print(statistics.median(num)*2-2)
else:
    print(statistics.median_low(num) + statistics.median_high(num) -2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import math
import itertools
def factorize(n):
    b = 2
    fct = []
    fct.append(1)
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

N = int(input())
listN = factorize(N)
x = 0
y = 0
L = [True for i in range(N*N)]
mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(1,len(listN)):
        tmp = list(itertools.combinations(listN,i))
        tmp = list(set(tmp))
        for j in range(len(tmp)):
            x0,y0 = 1,1
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                if L[x0]:
                    L[x0] = False
                    y0 = N//x0
                    if mini > abs(x0+y0):
                        mini = abs(x0+y0)
                        x = x0
                        y = y0
print(x-1+y-1)

Submission status: Time Limit Exceeded

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

n = int(input())

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

a = factorization(n)
fac = []
for i in a:
    for j in range(i[1]):
        fac.append(i[0])

x = 10**13
for i in range(int(len(fac)// 2 + 1)):
    p = list(itertools.permutations(fac, i))
    for j in range(len(p)):
        temp = 1
        for k in range(i):
            temp *= p[j][k]
        if x > abs(n / temp - temp):
            x = abs(n / temp - temp)
            ans = temp

print(int(n/ans + ans - 2))

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import math
import itertools
def factorize(n):
    b = 2
    fct = []
    fct.append(1)
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

N = int(input())
listN = factorize(N)
x = 0
y = 0
mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(1,len(listN)):
        tmp = list(itertools.combinations(listN,i))
        tmp = list(set(tmp))
        for j in range(len(tmp)):
            x0,y0 = 1,1
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                y0 = N//x0
                if mini > abs(x0+y0):
                    mini = abs(x0+y0)
                    x = x0
                    y = y0
print(x-1+y-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    N = int(input())
    nmin = 10**12
    maxI = max(2, N//2)
    for n in range(1, maxI):
        if N % n == 0:
            nmin = min(nmin, n + N//n - 2)

    print(nmin)

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


if __name__ == '__main__':
    N = int(input())
    prime = prime_factorize(N)
    res = N - 1
    for i in range(2**(len(prime)-1)):
        a = 1
        b = 1
        for j in range(len(prime)):
            if i & (1 << j):
                a *= prime[j]
            else:
                b *= prime[j]
        res = min(res, a+b-2)
    print(res)

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())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  for j in range(i, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
      break
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
bl = 0
i = 1
j = 1
a = 0
change_direction = 0
while bl == 0:
    if n == i * j:
        bl = 1
    else:
        if change_direction == 0:
            i = i + 1
            change_direction = 1
            a = a + 1
        else:
            j = j + 1
            change_direction = 0
            a = a + 1

print (a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 1 + n
if n % 2 == 0:
    max = int(n / 2)
else:
    max = int((n - 1) / 2)

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

print(int(ans - 2))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
a = int(input())
b = round(math.sqrt(a))
while a % b != 0:
    b+=1
c = int(a / b)
print(b+c-2)

Submission status: Time Limit Exceeded

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

A = []
for h in range(1, int(N/2)+1):
    if N % h == 0:
        A.append(h + int(N/h))

C = min(A)
print(C - 2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 1 + n
if n % 2 == 0:
    max = int(n / 2)
else:
    max = int((n - 1) / 2)

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

print(int(ans - 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
  
n = int(input())
d = make_divisors(n)
d.sort()
a = []
for i in range(len(d)-1):
  for j in range(i, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

print(a[ind][0]+a[ind][1]-2)

Submission status: Time Limit Exceeded

Solution code:
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.extend([b]*e)
        b, e = b + 1, 0
    if n > 1:
        fct.extend([n]*1)
    return fct

N = int(input())
arr = factorize(N)
M = len(arr)
ans = N
for i in range(2**M):
    A = 1
    B = 1
    for j in range(M):
        if (i>>j)&1:
            A *= arr[j]
        else:
            B *= arr[j]
    A = max(A-1,0)
    B = max(B-1,0)
    ans = min(ans,A+B)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
for i in range(2,n):
    for j in range(2,n):
        l.append(i*j)
if n not in l:
    ans = n-1
else:
    lf = []
    for k in range(1, n+1):
        if n % k == 0:
            lf.append(k)
        i = lf[len(lf) // 2 - 1]
        j = lf[len(lf) // 2]
        ans = i + j - 2
print(ans)

Submission status: Time Limit Exceeded

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

A = []
for h in range(1, N+1):
    if N % h == 0:
        A.append(h + int(N/h))

C = min(A)
print(C - 2)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import sys
array = []

for i in range(1,n+1):
    if n % i == 0:
      array.append(i)
if len(array)%2==1:
  a=array[int(len(array)/2)]
  print(2*a-2)
else:
  a=array[int(len(array)/2)-1]
  b=array[int(len(array)/2)]
  ans=a-1+b-1
  print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = 0
ans = 10000000000000000
s = 0
if N%2==0:
    for x in range(1,(N//2)+1):
        s=N//x
        if N%x==0:
            a = (s-1)+(x-1)
            if ans>a:
                ans = a
else:
    for x in range(1,((N+1)//2)):
        s =N//x
        if N%x==0:
            a = (s-1)+(x-1)
            if ans>a:
                ans = a
print(ans)

Submission status: Time Limit Exceeded

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

if len(prime_factorize(n)) == 1:
  print(n - 1)
  exit()

ret = None
min_r = n
for x in range(1, int( n / 2)):
  q, mod = divmod(n, x)
  _min_r = (2 * x - 2) + (q - x)
  if mod == 0 and min_r > _min_r:
    min_r = _min_r
    ret = (x, q)

print(min_r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
def p(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())
p=p(n)
if len(p)==1:
    print(p[0]-1)
    exit()
a=10**12
b=1
for i in p:
    b*=i
for k in range(int(len(p)**0.5),len(p)):    
    for i in itertools.combinations(p, k):
        c=np.prod(i)
        a=min(a,c+b//c)
print(a-2)

Submission status: Time Limit Exceeded

Solution code:
import statistics
import sys

a = int(input())
num = []
for i in range(a):
    if a % (i+1) == 0:
        num.append(i+1)

if isinstance(statistics.median(num), int):
    print(statistics.median(num)*2-2)
else:
    mid = len(num) / 2
    print(num[round(mid)-1] + num[round(mid)] -2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

rst = N - 1
for i in range(2,N):
    if (N % i) == 0:
        tmp = (i - 1) + ((N / i) - 1)
        if tmp < rst:
            rst = tmp
print("{0:.0f}".format(rst))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import math
import itertools

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

N = int(input())
listN = factorize(N)
x = 0
y = 0
L = [True for i in range(N*N)]
mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(1,len(listN)):
        tmp = list(itertools.combinations(listN,i))
        for j in range(len(tmp)):
            x0,y0 = 1,1
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                if L[x0]:
                    y0 = N//x0
                    if mini > abs(x0+y0):
                        mini = abs(x0+y0)
                        x = x0
                        y = y0
                        L[x0] = False
print(x-1+y-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
def factorize(n):
    b = 2
    fct = []
    end = int(n ** (0.5)) + 2
    for b in range(2, end):
      while n % b == 0:
        n //= b
        fct.append(b)
      if n == 1:
        break
    if n > 1:
      fct.append(n)
    return fct

fact = factorize(n)
dif = []
from itertools import combinations as com
for i in range((len(fact) + 1) // 2 + 1):
  for cands in com(fact, i):
    ans = 1
    for cand in cands:
      ans *= cand
    dif.append(n//ans + ans - 2)
print(min(dif))

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


if __name__ == '__main__':
    N = int(input())
    prime = prime_factorize(N)
    res = N - 1
    for i in range(2**len(prime)):
        a = 1
        b = 1
        for j in range(len(prime)):
            if i & (1 << j):
                a *= prime[j]
            else:
                b *= prime[j]
        res = min(res, a+b-2)
    print(res)

Submission status: Time Limit Exceeded

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

a = np.floor(np.sqrt(N))
while True:
  if N%a==0:
    break
  a=a-1
b=N/a
print(int(a+b-2))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
m = 1+n-2
i = 1
while i<=n:
    j = 1
    while j<=i:
        if i*j==n:
            c = i+j-2
            if c<m:
                m = c
        j+=1
    i+=1
print(m)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
target = int(input())
curAns = 10 ** 12
 
for i in range(1,target):
  if target % i == 0:
    j = target // i
    if (i+j-2) < curAns:
      curAns = i+j-2
print(curAns)

Submission status: Time Limit Exceeded

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

a = factorize(n)
m = len(a)
ans = 0
if m==1:
    print(a[0]-1)
elif m==2:
    print(a[0]+a[1]-2)
elif m==3:
    z = a[0]*a[1]
    print(z+a[2]-2)
else:
    ans = 10**12
    for i in range(2**m):
        x = 1
        y = 1
        for j in range(m):
            if ((i>>j)&1):
                x *=a[j]
            else:
                y*=a[j]
        ans = min(ans, x+y-2)
    print(ans)

Submission status: Time Limit Exceeded

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

a = int(math.sqrt(n))
for j in range(a,n):
	if n%j == 0 and n/j >0:
		print(int(n/j+j-2))
		break