Problem:


Score : 300 points

Problem Statement

Takahashi is standing on a multiplication table with infinitely many rows and columns.

The square (i,j) contains the integer i \times j. Initially, Takahashi is standing at (1,1).

In one move, he can move from (i,j) to either (i+1,j) or (i,j+1).

Given an integer N, find the minimum number of moves needed to reach a square that contains N.

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the minimum number of moves needed to reach a square that contains the integer N.

Sample Input 1

10

Sample Output 1

5

(2,5) can be reached in five moves. We cannot reach a square that contains 10 in less than five moves.

Sample Input 2

50

Sample Output 2

13

(5, 10) can be reached in 13 moves.

Sample Input 3

10000000019

Sample Output 3

10000000018

Both input and output may be enormous.



Sample input:
10


Sample output:
5

Submission status: Wrong Answer

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

sosu_dict = {}
a = N
b = 0
for i in range(1, int(math.sqrt(N+1))):
    if a % i == 0:
        sosu_dict[i] = int(a/i)
        b = a/i
 

if b > 1:
    sosu_dict[int(b)] = int(a/b)

#print(sosu_dict)

sum = 10 ** 12 +1
for key in sosu_dict:
    if key + sosu_dict[key] < sum:
        sum = key + sosu_dict[key]

print(sum-2)

Submission status: Wrong Answer

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


soinsu_list = sorted(soinsu(int(input())))
result = [1, 1]
for s in reversed(soinsu_list):
    if result[0] <= result[1]:
        result[0] *= s
    else:
        result[1] *= s
print(result[0] - 1 + result[1] - 1)

Submission status: Wrong Answer

Solution code:
n = int(input())

min = 10**12

for i in range(2,n):
  mod = n % i
  if mod != 0.0 : continue
  
  v1 = i
  v2 = int (n / i)

  move = ( v1 -1 ) + ( v2 - 1 )
  
  if move < min : move = min
    

print(min)

Submission status: Wrong Answer

Solution code:
n = int(input())

# コピー
m = 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)

# ans = -1

# for x in a:
#   y = m // x
#   if ans < 0 or ans < x + y:
#     ans = x + y


b = len(a) // 2
x = 1
for i in range(b):
  x *= a[i]
y = m // x
ans = x + y -2

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    ff = 3
    while ff * ff <= n:
        if n % ff == 0:
            a.append(ff)
            n //= ff
        else:
            ff += 2
    if n != 1:
        a.append(n)
    return a

f = []
serch_mini = []


for i in range(len(prime_factorize(N))):
    f = prime_factorize(N)
    b = f[0:i+1]
    c = f[i+1:]
    bb = 1
    cc = 1
    for j in range(len(b)):
        bb *= b[j]
    for k in range(len(c)):
        cc *= c[k]
    serch_mini.append(bb+cc)

print(min(serch_mini)-2)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
dis=N-1

for i in range(2,int(math.sqrt(N))+1):
    if N%i==0:
        if ((N/i)-1)+(i-1)<dis:
            dis=((N/i)-1)+(i-1)
        else:
            pass
    else:
        pass
print(dis)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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())
arr_N = prime_factorize(N)
arr_N_r = sorted(arr_N, reverse=True)
a = [1, 1]
last_i = 0

for i in range(len(arr_N) // 2):
    if i %2 == 0:
        a[0] = a[0] * arr_N[i] * arr_N_r[i]
        last_i = i
    if i %2 == 1:
        a[1] = a[1] * arr_N[i] * arr_N_r[i]
        last_i = i

if len(arr_N) % 2 == 1 and last_i %2 == 0:
    a[1] = a[1] * arr_N[len(arr_N) // 2]
if len(arr_N) % 2 == 1 and last_i %2 == 1:
    a[0] = a[0] * arr_N[len(arr_N) // 2]


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

Submission status: Wrong Answer

Solution code:
N = int(input())
l = []
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)

print(l[len(l)-1] - 1 + l[len(l) - 2] - 1)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
import sys
sys.setrecursionlimit(1000000)
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

list1 = prime_factorize(n)
list1.reverse()
flag = 1
a,b = 1,1
for i in range(len(list1)):
	if a*list1[i] <= b*list1[i]:
		a *= list1[i]
	else:
		b *= list1[i]
	

print((a-1)+(b-1))

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
m=math.sqrt(n)
m=math.floor(m)+1
li=[]
for i in range(1,m):
    a=i+n/i
    li.append(a)
li=[li[i] for i in range(m-1) if li[i].is_integer()]
print(int(min(li))-2)
print(li)

Submission status: Wrong Answer

Solution code:
n = int(input())

li = [0 for i in range(50)]
x = 2
y = 0
while n >= x and x <= 10**6:
    if n % x == 0:
        n /= x
        li[y] = x
        y += 1
    else:
        x += 1

li.sort(reverse=True)
pair=[1,1]
if li[0]!=0:
    for i in range(50):
        if li[i]!=0:
            if pair[0]<=pair[1]:
                pair[0]*=li[i]
            else:
                pair[1]*=li[i]
    print(sum(pair)-2)
else:
    print(n-1)

Submission status: Wrong Answer

Solution code:
N = int(input())

tmp = []
for i in range(1,500):
    if N % i == 0:
        tmp.append((i, N//i))

res = 100000000000
for i, x in tmp:
    Min =  (i-1) + (x-1)
    if res > Min:
        res = Min

print(res)

Submission status: Wrong Answer

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

    # divisors.sort()
    return divisors

N = int(input())

n = make_divisors(N)
n.sort()
mannaka_ = int(len(n)/2)
mannaka = mannaka_ - 1

if len(n)%2 == 0:
    print((n[mannaka_]-1)+ (n[mannaka]-1))
else:
    print(n[mannaka_] * 2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


n = int(input())
b = prime_factorize(n)
if len(b) == 1:
    print(b[0] - 1)
    exit()
x = 1
y = 1
b = sorted(b, reverse=True)
for i in range(0, len(b)):
    if x <= y:
        x *= b[i]
    else:
        y *= b[i]
print(x+y-2)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math

def main(N):
    min_dis = None
    for i in range(1, int(math.log(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: Wrong Answer

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
Nfac=prime_factorize(N)
while len(Nfac) > 2:
  NewNfac = []
  mini=(min(Nfac))
  Nfac.remove(min(Nfac))
  mini2=(min(Nfac))
  prod=mini*mini2
  Nfac.remove(min(Nfac))
  Nfac.append(prod)
else:
  if len(Nfac)==1:
    print(Nfac[0]-1)
  else:
    print(Nfac[0]+Nfac[1]-2)

Submission status: Wrong Answer

Solution code:
import sys
def is_prime(n):
    if n == 1:
        return False
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

def prime_factors(n):
    prime_factor_list = []
    while not n % 2:
        prime_factor_list.append(2)
        n //= 2
    while not n % 3:
        prime_factor_list.append(3)
        n //= 3
    i = 5
    while n != 1:
        if is_prime(i):
            while not n % i:
                prime_factor_list.append(i)
                n //= i
        i += 2

    return prime_factor_list


for line in sys.stdin:
    N = int(line)

    factors = prime_factors(N)

    a = 1
    b = 1
    for i in range(0, len(factors), 2):
        if i == len(factors)-1:
            a *= factors[i]
        else:
            a *= factors[i]
            b *= factors[i+1]

    print(a+b-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
import math
import itertools
def is_prime(n):
   if n == 1: return False
   for k in range(2, int(math.sqrt(n)) + 1):
      if n % k == 0:
         return False
   return True

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])  
         arr.append([i]*cnt)     

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

   arr=list(itertools.chain.from_iterable(arr))

   a=1
   b=1
   # ss=0
   s=0
   # print(arr)
   for i in range(len(arr)):
      if arr[i] < arr[-1]:
         a = a * arr[i]
         # print(a)
      else:
         b=b*arr[i]
         # print(b)
      # if i % 2 !=0:
      #    b = b*arr[i]
      # else:
      #    a=a*arr[i] 
   s=(b-1)+(a-1)
   # print("a,b:",a,b)
   return s
   # return [a,b]


if is_prime(n):
   print(n-1)
else:
   a=factorization(n)

   print(a)

Submission status: Wrong Answer

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

    # divisors.sort()
    return divisors

N = int(input())

n = make_divisors(N)
n.sort()
mannaka_ = int(len(n)/2)
mannaka = mannaka_ - 1
print(n)
if len(n)%2 == 0:
    print((n[mannaka_]-1)+ (n[mannaka]-1))
else:
    print(n[mannaka_] * 2)

Submission status: Wrong Answer

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 prod(n):
  result = 1
  for x in n:
    result *= x
  return result
  
a = prime_factorize(n)
b = [a.pop(-1)]


while prod(a) > prod(b):
  prev_result = prod(a) + prod(b)
  b.append(a.pop(0))

try:
  if prev_result < prod(a) + prod(b):
    a.append(b.pop(-1))

except:
  pass
print(prod(a)-1 +prod(b)-1)

Submission status: Wrong Answer

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


if __name__ == '__main__':
    N = int(input())
    prime = prime_factorize(N)
    res = N - 1
    aa = prime.pop(0)
    if not prime:
        print(res)
        exit()
    for i in range(2**(len(prime)-1)):
        a = aa
        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: Wrong Answer

Solution code:
import math

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

if n == 2:
  print(0)
  exit()

l = make_divisors(n)

ans = n-1
for i in range(0, len(l)):
  for j in range(0, len(l)):
    a = l[i]
    b = l[j]
    if a * b == n:
      ans = min(ans, (a+b-2))

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math

def main(N):
    min_dis = None
    for i in range(1, int(math.sqrt(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: Wrong Answer

Solution code:
import math
N = int(input())
k = math.sqrt(N)
z = math.floor(k)

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1

if is_prime(N) == 1:
    print(N-1)
elif z < k:
    r = (z*2) - 1
    print(r)
else:
    r = (z*2) - 2
    print(r)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
sq = math.floor(pow(n, 0.5))
flg = False
for i in range(2, sq + 1):
    if n % i == 0:
        flg = True
        break
if flg:
    print(((sq - 1) * 2) + (n - sq**2))
else:
    print(n - 1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import math

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())
A_tmp = prime_factorize(N)
N_tmp, N_tmp1, N_tmp2= 0, 1, 1
total_num = 1
tmp, max_num = 1, 0
A_len = len(A_tmp)

for i in range(A_len):
    total_num = total_num * A_tmp[i]

for i in range(len(A_tmp)):
    for j in range(len(A_tmp) - i):
        tmp = tmp * A_tmp[i + j]
        if tmp > int(math.sqrt(N)):
            tmp = tmp // A_tmp[i + j]
            if max_num < tmp:
                max_num = tmp
    tmp = 1
print(max_num + (total_num // max_num) - 2)

Submission status: Wrong Answer

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)

A = []
B = []
for i, v in enumerate(p[::-1]):
    if i % 2:
        A.append(v)
    else:
        B.append(v)

if len(B) > len(A):
    A.append(1)
from itertools import product
S = N + 1
for l in product([0,1], repeat=len(A)):
    a = b = 1
    for i, v in enumerate(l):
        if v:
            a *= A[i]
            b *= B[i]
        else:
            a *= B[i]
            b *= A[i]
    S = min(S, a+b)
print(S-2)

Submission status: Wrong Answer

Solution code:
n = int(input())

a_list = []
b_list = []

for a in range(1,n+1):
  if n % a == 0:
    b = n / a
  a_list.append(a)
  b_list.append(b)

sum_list = []
for a,b in zip(a_list,b_list):
  sum_list.append(a+b-1)
print(int(min(sum_list)))

Submission status: Wrong Answer

Solution code:
import math

def divisor_generator(n):
    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            large_divisors.append(n // i)
    for divisor in reversed(large_divisors):
        yield divisor

n = int(input())


divs = list(divisor_generator(n))
print(divs)
l = len(divs) - 1
best = 2 if n == 1 else min([divs[i] + divs[l-i] for i in range(len(divs)>>1)] )

print(best-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = 1
while a**2<=n:
  a += 100
ans = n
for i in range(a):
  if n % (int(i)+1) == 0:
    b = n/(int(i)+1) + (int(i)+1) -2
    if b < ans:
      ans = b
      
print(ans)

Submission status: Wrong Answer

Solution code:
def factorize(n):
    b = 2.0
    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

n = float(input())
temp = 1.0

n = factorize(n)

n.sort()
last = n.pop(-1)
for i in n:
    temp = temp * i
print(int((last-1)+ (temp-1)))

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
t=int(math.sqrt(n))
i=1
j=0
count=0
while count==0:
    if i>t:
        break
    j+=1
    for a in range(i):
        #print('i=', i)
        #print('a+1=', a+1)
        #print('j=', j)
        #print('a+1*j=', (a+1)*j)
        if (a+1)*j==n:
            count+=1
            i=a+1
            #print('ok')
            break
    else:
        i+=1
        continue
    break
#print('i=', i+1)
#print('j=', j+1)
print(i+j-2)

Submission status: Wrong Answer

Solution code:
N = int(input())
def trial_division(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

T = trial_division(N)
D = {}
for t in T :
    if t not in D :
        D[t] = 1
    else :
        D[t] += 1

S = set()
for t in T :
    for i in range(D[t]+1) :
        if t**i == 1 or t**i == N :
            S.add((t**i)+(N//(t**i))-2)
        else :            
            S.add((t**i)+(N//(t**i))-2)
ans = min(list(S))
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def isPrime(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n % k == 0:
            return False
    return True
def searchMaxNum(n):
    max = 0
    for k in range(2, int(math.sqrt(n))+1):
        if n % k == 0:
            max = k
    return max
n = int(input())
r = isPrime(n)
m = searchMaxNum(n)
if r == True:
    print(n-1)
else:
    print((m-1)+(n/m-1))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

i = 1
answer = N - 1
while i * i <= N:
    if N % i == 0:
        new_answer = (i - 1) + ((N / i) - 1)
        if answer > new_answer:
            answer = new_answer
    i += 1

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())

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)

# print(fct)
c = Counter(fct)


# 16 4 * 4    2 2 2 2
# 36 6 * 6    2 2 3 3

# print(c)
# print(list(c.items()))
flag = True
for i in list(c.keys()):
    # print(c[i])
    if c[i] % 2 != 0:
        flag = False
        break

if not flag:
    a = 1
    for i in range(len(fct) - 1):
        a *= fct[i]

    print(a + fct[-1] - 2)
    exit()

if flag:
    tmp = list(c.items())
    if len(tmp) == 1:
        a = tmp[0][0] ** (tmp[0][1]/2)
        # print(tmp[0][0])
    if len(tmp) == 2:
        a = tmp[0][0] * tmp[1][0]
    # print(tmp)
    # a = tmp[0] * tmp[1]
    # print(a)
    print(a + a - 2)

Submission status: Wrong Answer

Solution code:
import math
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)
  if temp!=1:
    arr.append(temp)
  if arr==[]:
    arr.append(n)
  return arr


def main():
  x = int(input())
  factorized = factorization(x)
  factorized.reverse()
#  i = 0
  a = 1
  b = 1
  for num in factorized:
    if a < b:
      a = a * num
    else:
      b = b * num
#    i += 1
  result = a - 1 + b - 1
  return result
print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i==0:
			cnt=0
			while tmp%i==0:
                		cnt+=1
                		tmp //= i
			for k in range(cnt):
            			arr.append(i)
	if tmp!=1:
		arr.append(tmp)
	if arr==[]:
		arr.append(n)
	return arr

n = int(input())

fac = factorization(n)
if len(fac) == 1:
	print(fac[0]-1)
	exit()
dfac=deque(fac)
a=dfac.pop()
b=1
for i in range(len(fac)-1):
	if a > b:
		b *= dfac.pop()
	else:
		a *= dfac.pop()

print("%d" % (a+b-2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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())
arr_N = prime_factorize(N)
arr_N_r = sorted(arr_N, reverse=True)

a = [1, 1]

for i in range(len(arr_N) // 2):
    if i %2 == 0:
        a[0] = a[0] * arr_N[i] * arr_N_r[i]
    if i %2 == 1:
        a[1] = a[1] * arr_N[i] * arr_N_r[i]

if len(arr_N) % 2 == 1:
    a[1] = a[1] * arr_N[len(arr_N) // 2]

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

Submission status: Wrong Answer

Solution code:
# coding:utf-8

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

res = factorization(N)

if len(res) == 0:
    print(0)
elif len(res) == 1:
    print(N-1)
elif len(res) == 2 and res[0][1] == 1 and res[1][1] == 1:
    print(res[0][0] + res[1][0] - 2)
else:
    l = [pair[0] for pair in res for _ in range(pair[1])]
    binary = [str(bin(i)).lstrip('0b') for i in range(1, 2**len(l)-1)]
    b_len = len(binary[-1])
    binary = [el.zfill(b_len) for el in binary]
    minimum = N
    stack = []
    tmp1 = tmp2 = 1
    for combi in binary:
        for i, bit in enumerate(combi):
            if bit == '0':
                tmp1 *= l[i]
            else:
                tmp2 *= l[i]
        if tmp1 in stack:
            continue
        else:
            if tmp1 + tmp2 < minimum:
                minimum = tmp1 + tmp2
        stack.append(tmp1)
        tmp1 = tmp2 = 1
    print(minimum - 2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
target = int(input())
curAns = 10 ** 12

for i in range(1,int(math.sqrt(target))):
  if target % i == 0:
    j = target // i
    if (i+j-2) < curAns:
      curAns = i+j-2
print(curAns)

Submission status: Wrong Answer

Solution code:
import sys
import math
ab = []
abc= []
def divisor(n):
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ab.append(i)
            if i**2 == n:
                continue
            abc.append(n//i)
a = input()
a = int(a)
divisor(a)
abcd = []
k = 0
for k in ab:
 for s in abc:
  abcd.append(k+s)
d = abcd.index(min(abcd))
#print(ab[d])
#print(abc[d])
print(ab[d]+abc[d]-2)

Submission status: Wrong Answer

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

def is_prime(n):
    if n == 1: return 0
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0

    return 1

flag = is_prime(n)

if flag == 1:
    print(n-1)
else:
    if math.sqrt(n) == n/math.sqrt(n):
        print(int((math.sqrt(n)-1)*2))
    else:
        m = int(n/2)
        for i in reversed(range(2,m+1)):
            if n % i == 0:
                l = i
                break
        s = int((n/l)+l-2)
        print(s)

Submission status: Wrong Answer

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

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

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

    return arr

N = int(input())

arr = factorization(N)

#print(arr)

li = []

for i in arr:
    for j in range(i[1]):
        li.append(i[0])
#print(li)
while(len(li) > 2):
    li.sort()
    li.append(li[0]*li[1])
    li.pop(0)
    li.pop(0)
    #print(li)
#print(li)
if(len(li) == 1):
    print(li[0]-1)
else:
    print(li[0]+li[1]-2)

Submission status: Wrong Answer

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

    # divisors.sort()
    return divisors

N = int(input())

maxStep = N

divs = make_divisors(N)

for i in range(round(len(divs)/2)):
	if 2*i+1 >= int(len(divs)):
		A=divs[2*i]
		B=divs[2*i]
	else:
		A=divs[2*i]
		B=divs[2*i+1]
	if  A-1 + B-1 < maxStep:
		maxStep = A-1 + B-1

print(maxStep)

Submission status: Wrong Answer

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(i-2+(a/i))
        else:
            print(a-1)
        break

Submission status: Wrong Answer

Solution code:
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass



n = int(input())
l = sorted(divisor(n))
print(l[(len(l)//2 - 1)] + l[(len(l)//2)] - 2)

Submission status: Wrong Answer

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


n = int(input())
b = prime_factorize(n)
if len(b) == 1:
    print(b[0] - 1)
    exit()
x = 1
y = 1
for i in range(1, len(b)+1):
    if x <= y:
        x *= b[-i]
    else:
        y *= b[-i]
print(x+y-2)

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = 0

for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        x = i
        if i != n // i:
            y = n//i
            if ans == 0 or ans > x + y:
                ans = x + y
                a = x
                b = y
            elif ans < x + y:
                print(a + b - 2)
                exit()

print(a + b - 2)

Submission status: Wrong Answer

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

    # divisors.sort()
    return divisors

N = int(input())

maxStep = N-1

divs = make_divisors(N)

for i in range(round(len(divs)/2)):
	if 2*i+1 >= int(len(divs)):
		A=divs[2*i]
		B=divs[2*i]
	else:
		A=divs[2*i]
		B=divs[2*i+1]
	if  A-1 + B-1 < maxStep:
		maxStep = A-1 + B-1

print(maxStep)

Submission status: Wrong Answer

Solution code:
import itertools
import operator
import functools

def 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

target_list = factorize(int(input()))
loop=len(target_list)+1
ans=pow(10,24)

for i in range(loop):
    a=target_list[:i]
    b=target_list[i:]
    if len(a)>0:
        a=functools.reduce(lambda x,y:x*y,target_list[:i])
    else:
        a=1
    if len(b)>0:    
        b=functools.reduce(lambda x,y:x*y,target_list[i:])
    else:
        b=1
    ans=min(ans,a+b-2)

print(ans)

Submission status: Wrong Answer

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

n=int(input())
A=prime_factorize(n)
x,y=1,1
for i in A[::-1]:
    if x<=y:x *=i
    else:y *=i
print(x+y-2)

Submission status: Wrong Answer

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(len(a) // 3,2*len(a) // 3+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: Wrong Answer

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

    # divisors.sort()
    return divisors

divisor_list = make_divisors(int(input()))
print(divisor_list[-1]+divisor_list[-2]-2)

Submission status: Wrong Answer

Solution code:
import itertools
from functools import reduce

N = int(input())

def prime_f(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
    
A = prime_f(N)

F = []
L = []

distance = []

for i in range(1,len(A)):
  F = A[0:i]
  L = A[i:len(A) + 1]
  totalF = reduce(lambda x,y:x*y,F)
  totalL = reduce(lambda x,y:x*y,L)
  distance.append(totalF + totalL)
  
if len(A) == 1:
  print(N - 1)
else:
  print(min(distance) - 2)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=1
mini=1e+12
for i in range(2,int(math.sqrt(n))+1):
    while n%i==0:
        a*=i
        n//=i
        if a-1+n-1<mini:
          mini=a-1+n-1
print(mini)

Submission status: Wrong Answer

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

D=2*math.sqrt(N)
Dint=0
if(D>int(D)):
    Dint=int(D)+1
else:
    Dint=int(D)

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