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

N = int(input())

i = 1
j = 1


n = 0
factors = factorization(N)
#print(factors)

min_n = 0
f_list = []
for fnum, factor in enumerate(factors):
    base = factor[0]
    exp  = factor[1]
    for e in range(exp):
        f_list.append(base)

#print(f_list)
min_n = 1001001001001

#print("perm: ", list(itertools.permutations(f_list)) )
#print("perm: ", set(list(itertools.permutations(f_list))) )

for f in set(list(itertools.permutations(f_list))):
    #print(f)
    fl = list(f)
    #print(fl)
    i = 1
    for a in range(len(fl)):
        #print(a, fl)
        i = i * fl[a]
        j = 1
        for b in range(a+1, len(fl)):
            #print(a, fl)
            j = j * fl[b]
        n = (i-1) + (j-1)
        #print("i, j, (n): ", i, j, n)
        if n < min_n:
            min_n = n
#    n = n + ((factor[0]* factor[1]-1) )

print(min_n)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

N = int(input())

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

n = prime_factors(N)

dicts = {}
for x in range(2**len(n)):
    flgs = bin(x)[2:]
    if len(flgs) < len(n):
        flgs = ''.join(['0' for _ in range(len(n)-len(flgs))]) + flgs
    flgs = flgs[::-1]
    
    a = 1
    b = 1
    for i in range(len(flgs)):
        if flgs[i] == '1':
            a *= n[i]
        else:
            b *= n[i]
    dicts[a+b] = {'a':deepcopy(a), 'b':deepcopy(b)}

            
min_ab = min(dicts.keys())
print(dicts[min_ab]['a'] + dicts[min_ab]['b'] - 2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

min = 10 **12
for j in lst:
    if min >= (j[0] + j[1] - 2):
        min = j[0] + j[1] - 2
print(min)

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(len(fac) + 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:
n = int(input())
ans = 1 + n
if n % 2 == 0:
    max = int(n / 2 + 1)
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:
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))
        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())

def prime_factorize(num):
    """
    This function performs prime factorization on the input natural number.
    The result is returned in the form of a dictionary with the prime number as the key
    and its number as the value.
    :param num:
    :return prime_factor: Dictionary with the prime number as the key and its number as the value.
    """
    prime_factor = {}
    i = 2
    while i ** 2 <= num:
        while num % i == 0:
            num //= i
            if i in prime_factor.keys():
                prime_factor[i] += 1
            else:
                prime_factor[i] = 1
        i += 1
    if num > 1:
        prime_factor[num] = 1
    return prime_factor

res = prime_factorize(N)

tar = []

for k, v in res.items():
    for j in range(v):
        tar.append(k)

n = len(tar)
ans = N -1
for bit in range(1<<n):
    x = 1
    y = 1
    for i in range(n):
        if bit & (1 << i):
            x *= tar[i]
        else:
            y *= tar[i]
    cnt = 0
    if x != 1:
        cnt += x - 1
    if y != 1:
        cnt += y -1
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = n
b = 1
try:
    for i in range(1,n//2):
        if n%i==0:
            if abs((n//i) - i) <= abs(a-b):
                a = n//i
                b = i
    print(a+b-2)
except:
    print(n-1)

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

def split(ary, a, b, i):
    if len(ary) == i:
        if a == 1 or b == 1:
            return a + b - 1
        else:
            return a + b - 2
    v = ary[i]

    v1 = split(ary, a * v, b, i+1)
    v2 = split(ary, a, b * v, i+1)
    return min(v1, v2)

ary = prime_factorize(N)

if len(ary) == 1:
    print(str(ary[0] - 1))
elif len(ary) == 2:
    cost = ary[0] + ary[1] - 2
    print(str(cost))
else:
    v = split(ary, 1, 1, 0)
    print(str(v))

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

# -------- #

data = int(input())
ng_flag = False
min_value = 9999999

if is_prime(data):
    print(data -1)
    exit(0)

for i in range(1, int(data / 2) + 1):
    if data % i == 0:
        validation = i + data / i
        if validation < min_value:
            min_value = validation
print(int(min_value-2))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

ya = []

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

lenarray=len(ya)
if lenarray%2==0:
  for i in range(lenarray//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)
else:
  for i in range((lenarray-1)//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)


  y=ya[0]
  answer.append(y*2)
  
print(min(answer)-2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
lists = []
for i in range(1, N+1) :
    A = int(i)
    if N % A == 0 :
        B = int(N/A)
        lists.append([A, B])
        
sums = []
for i in range(len(lists)) :
    sum = lists[i][0] + lists[i][1]
    sums.append(sum)

index = sums.index(min(sums))
choice = lists[index]
result = choice[0] + choice[1] - 2
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()
a = input()
a = int(a)
if  a == 1:
 print(1)
 sys.exit()
k = range(1,a)
resn =[]
for s in k:
 res = a/s
 #print("s",s)
 #print("res",res)
 try:
  res = int(res)
 except:
  break
 if is_integer(s):
  if is_integer(res):
   #if len(str(s)) == 1:
    #if len(str(res)) == 1:
     #print(res,s)
     if res * s == a:
      #print("Yes")
      resn.append(s+res)
      #sys.exit() 
#print("No")
print(min(resn)-2)

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

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:
N = int(input())
list_ans = list()
for i in range(1,int(N/2)):
  if N%i == 0:
    list_ans.append(i+N/i)
if not list_ans:
  print(N-1)
else:
  print(int(min(list_ans)-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:
    I=i
    J=N/i
    break
print(int(I-1+J-1))

Submission status: Time Limit Exceeded

Solution code:
import sys


n = int(input())

cost = sys.maxsize
tmp = 0

for i in range(1,n):
    if((n%i)==0):
        tmp = i + int(n/i) - 2
        cost = min(tmp,cost)
        tmp = 0

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import itertools

n = int(input())

def is_prime(n):
    for p in range(2, n):
        if n % p == 0:
            return 0
    return 1

a = is_prime(n)
if a == 1:
    print(n-1)
    sys.exit()


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

    return divisors

ans = make_divisors(n)
m = max(ans)
print( (m-1) + ans[m]-1)

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 main():
    N = int(input())

    x = prime_factorize(N)
    D = []
    for i in range(2 ** len(x)):
        a = format(i, '0{}b'.format(len(x)))
        D.append(a)

    # print(x)
    # print(D)

    mn = 1 + N
    for di in D:
        a = 1
        b = 1
        for i, dii in enumerate(di):
            if dii == '0':
                a = a * x[i]
            else:
                b = b * x[i]

            if a + b > mn:
                break
        mn = min(mn, a + b)
    print(mn - 2)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

l=1
f=False
while True:
    j=l+1
    for i in range(1,l+1):
        if n == i*(j-i):
            print(j-2)
            f=True
            break
    l+=1
    if f:
        break

Submission status: Time Limit Exceeded

Solution code:
import math

def eratosthenes(n):
    p_list = []
    root_n = math.sqrt(n)
    data = [i + 1 for i in range(1, n)] 
    while True:
        p = data [0]
        if root_n <= p:
            return p_list + data 
        p_list.append(p)
        data = [e for e in data if e % p != 0]

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

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

    if n in eratosthenes(n):
        print(n-1)
    else:
        a, b = make_divisors(n)
        a -= 1
        b -= 1
        print(a+b)
        
        
if __name__ == "__main__":
    main()

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 main():
    N = int(input())

    x = prime_factorize(N)
    D = []
    for i in range(2 ** len(x)):
        a = format(i, '0{}b'.format(len(x)))
        D.append(a)

    # print(x)
    # print(D)

    mn = 1 + N
    for di in D:
        a = 1
        b = 1
        for i, dii in enumerate(di):
            if dii == '0':
                a = a * x[i]
            else:
                b = b * x[i]

            if a + b > mn:
                continue
        mn = min(mn, a + b)
    print(mn - 2)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def prime_factorization(n):
    factor = []
    f = 2
    while f ** 2 <= n:
        if n % f == 0:
            factor.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        factor.append(n)
    return factor

p = prime_factorization(N)
from itertools import combinations as cb
from functools import reduce
from operator import mul

s = N+1
for i in range(1, len(p)//2+1):
    for j in cb(p, i):
        A = reduce(mul, j)
        B = N//A
        s = min(s, A+B)

print(s-2)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
b=[]
c=[]
d=0

for i in range(1,n):
    if n%i==0:
        a.append(int(n//i))
        b.append(i)
        d += 1

for i in range(d):
    c.append(a[i]+b[i])


print(min(c)-2)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    x = int(input())
    ans = x+2
    for i in range(x, 0, -1):
        if x % i == 0:
            q = (int(x/i) - 1) + (i-1)
            if q < ans:
                ans = q
            else:
                print((int(x/i) - 1) + (i-1))
                break

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

fact = factorize(n)
dif = []
from itertools import combinations as com
for i in range(len(fact) + 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:
N = int(input())
A = []
B = []
minP = N

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
c=0
INF=2000000
x=[]
y=[]

for i in range(N):
    if i*i>N : break
    for j in range(N-i) :
        if ((i+1)*(i+j+1))==N:
            x.append(i+1)
            y.append(i+j+1)
            c+=1


d=INF
for i in range(c):
    if d>(x[i]+y[i]):
        d=x[i]+y[i]-2

print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import itertools

n = int(input())

def is_prime(n):
    for p in range(2, n):
        if n % p == 0:
            return 0
    return 1

a = is_prime(n)
if a == 1:
    print(n-1)
    sys.exit()

l = []
# for i in range(2, n):
#     for j in range(2, n):
#         if i*j == n:
#             l.append((i-1)+(j-1))
#         else:
#             continue

# print(min(l))

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

    # divisors.sort()
    return divisors

ans = make_divisors(n)
print( (max(ans)-1) + ans[max(ans)]-1)

Submission status: Time Limit Exceeded

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

print(max_i + max_j - 2)

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(1,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 numpy as np

N = int(input())

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

factors = np.array(prime_factorize(N))
selectors = [np.array(list(map(bool, map(int, list("{0:b}".format(i).zfill(len(factors))))))) for i in range(2**len(factors))]
combinations = [(factors[selector].prod(), N//factors[selector].prod()) 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:
n = int(input())
a = n - 1
p = 1
for c in range(2, int(n / 2)):
    if p == 1 and c > (n ** 0.5):
        break
    if n % c == 0:
        p = c
        w = int(n / c)
        if (w + c - 2) < a:
            a = (w + c -2)
        else:
            continue
    else:
        continue
print(a)

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

l = factorize(n)


import itertools
c = list(itertools.product(range(2), repeat=len(l)))
#print(c)

flag = False
k = 10**15
for i in range((len(c)+1)//2):
    a = 1
    b = 1
    for j in range(len(c[i])):
        if c[i][j] == 0:
            a *= l[j]
        else:
            b *= l[j]
    k = min(k, a+b)
    if a == b:
        break
    

print(k-2)

Submission status: Time Limit Exceeded

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

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

B = []
for k in range(len(A)):
    B.append(A[k][0] + A[k][1])
C = min(B)
print(C - 2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

results = []
min = 10**12
index = -1

for v1 in range(1,10**12):
  for v2 in range(1,10**12):
    res = v1 * v2
    if res == n :
      results.append((v1,v2))
      
i = 0
for v1,v2 in results:
  move = (v1-1)+(v2-1)
  if move < min :
    min = move
    index = i
    i += 1
    
print(min)

Submission status: Time Limit Exceeded

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

for i in range (1, n+1):
    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 random

def miller_rabin(n, k=20):
    n = abs(n)
    if n == 2:
        return True
    elif n == 1 or n & 1 == 0:
        return False
    d = n - 1
    while d & 1 == 0:
        d = d >> 1
    for i in range(k):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = pow(y, 2, n)
            t = t << 1
        if y != n - 1 and t & 1 == 0:
            return False
    return True

i = int(input())

if miller_rabin(i):
    print(i - 1)
else:
    minimum = pow(10, 12)
    for x in range(1, i + 1):
        tmp = i / x
        if tmp.is_integer() is not True:
            continue
        if tmp == 1:
            continue
        if tmp + x < minimum:
            minimum = tmp + x

    print(int(minimum) - 2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

last_num = n // 2 + 1

can_division = []
min_ = 100000000000

for i in range(1, last_num):
    if n%i == 0:
        tmp = (i-1) + (n/i - 1)
        if tmp < min_:
            min_ = tmp
print(int(min_))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

c = 10**7

for a in range(2, (N+1)//2):
    if N % a == 0:
        b = N / a
        if (a-1)+(b-1) < c:
            c = (a-1)+(b-1)
        
print(min((N-1), int(c)))

Submission status: Time Limit Exceeded

Solution code:
# import sys
import numpy as np
# sys.setrecursionlimit(200000)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr


N = list(map(int, input().split(" ")))[0]

so = []
for n, i in (factorization(N)):
    for _ in range(i):
        so.append(n)
so = np.sort(so)[::-1]

l = len(so)

res = []

for i in range(1, 2 ** len(so) - 1):
    b = list(map(int, list(bin(i)[2:])))
    index = np.array([0] * (l - len(b)) + b, np.bool)
    A = np.cumprod(so[index])[-1]
    B = np.cumprod(so[~index])[-1]
    res.append(A + B - 2)

print(np.min(list(res) + [N - 1]))

Submission status: Time Limit Exceeded

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

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

def calc_dist(x, y):
	return abs(x - 1) + abs(y - 1)

n = int(input())
ll = prime_factorize(n)

min_dist = 10 ** 12
for bb in itertools.product([0, 1], repeat = len(ll)):
	l = 1
	r = 1
	for i in range(len(ll)):
		if bb[i] == 1:
			l *= ll[i]
		else:
			r *= ll[i]
	#print(bb, l, r, calc_dist(l, r))
	min_dist = min(min_dist, calc_dist(l, r))
print(min_dist)

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(1,len(p)):    
    for i in itertools.combinations(p, k):
        c=np.prod(np.asarray(i))
        a=min(a,c+b//c)
print(a-2)

Submission status: Time Limit Exceeded

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

print(max_i + max_j - 2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

print(m-2)

Submission status: Time Limit Exceeded

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

prime = prime_factorize(N)
min_cnt = 10**13
if len(prime) == 1:
    print(prime[0]-1)
else:
    for i in range(1,2 ** len(prime)-1):
        x = 1
        y = 1
        index = 0
        while index <= len(prime)-1:
            if i & 1 == 1:
                x *= prime[index] 
            else:
                y *= prime[index]
            i = i >> 1
            index += 1
        min_cnt = min(min_cnt, (x-1) + (y-1))
    print(min_cnt)

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
ans_L = []
d_L = []

tmp = n
for val in range(1,int(n/2)+1):
    if n % val ==0:
        x = val
        y = int(n/val)
        tmp = min(tmp,int(x+y-2))
print(tmp)

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 main():
    N = int(input())

    x = prime_factorize(N)
    D = []
    for i in range(2 ** len(x)):
        a = format(i, '0{}b'.format(len(x)))
        D.append(a)

    # print(x)
    # print(D)

    mn = 1 + N
    for di in D:
        a = 1
        b = 1
        for i, dii in enumerate(di):
            if dii == '0':
                a = a * x[i]
            else:
                b = b * x[i]
        # print(a, b)
        mn = min(mn, a + b)
    print(mn - 2)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
data = int(input())
ng_flag = False
min_value = 9999999
for i in range(1, data + 1):
    if data % i == 0:
        validation = i + data / i
        if validation < min_value:
            min_value = validation
print(int(min_value-2))

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 in range(b):
      if ((i >> j) & 1):
        _a*=a[j]
      else:
        _b*=a[j]
    ans=min(ans,_a+_b-2)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = []
for i in range(a):
  if a%(i+1)==0:
    b.append(i+1)
wa = 100000000000
for i in range(len(b)):
    wa1 = b[i] + b[len(b)-i-1]
    if wa >= wa1:
      wa = wa1
if len(b)%2==1:
  wa1 = b[int(len(b)/2) + 1] * 2
  if wa >= wa1:
    wa = wa1
print(wa-2)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for i in range(int(np.sqrt(N))):
    a=int(np.sqrt(N))-i
    if N%a==0:
        A=a
        B=N//a
        break
print(A+B-2)

Submission status: Time Limit Exceeded

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

print(m-2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
counting = True
divide = 1
insuu_list = []
for i in range(1, N+1):
  if N % i == 0:
    insuu_list.append([i, N / i])

dist_list = []
for j in range(len(insuu_list)):
  dist_list.append(insuu_list[j][0] - 1 + insuu_list[j][1] -1)

print(int(min(dist_list)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(1,math.floor(n*0.5)+1):
  if (n/i)%1==0:
    j=n/i
    list.append(i+j)

print(int(min(list)-2))

Submission status: Time Limit Exceeded

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