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 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())
data=prime_factorize(N)
a=1
b=1
import math
sq=math.sqrt(N)
for i in range(len(data)):
  if a<sq:
    a*=data[i]
  else:
    b*=data[i]

print(a+b-2)

Submission status: Wrong Answer

Solution code:
words = lambda t : list(map(t, input().split()))
n = int(input())


import math
def prime_factors(n):
    pfs = []
    m = int(math.sqrt(n)) + 1
    for num in range(2,m):
        if n % num == 0:
            while n % num == 0:
                n //= num
                pfs.append(num)
    if not n == 1:
        pfs.append(n)
    return pfs

pfs = prime_factors(n)
print(pfs)

pfs = reversed(sorted(pfs))
x = 1
y = 1
for pf in pfs:
    if x * pf + y <= y * pf + x:
        x *= pf
    else:
        y *= pf
print(x + y - 2)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

min = 10 ** 12
for i in range(0, len(cd) - 1,  2):
    if cd[i] + cd[i+1] < min:
        min = cd[i] + cd[i+1]

print(min - 2)

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)
flag = 1

a,b = 1,1
for i in range(len(list1)):
	if flag:
		a *= list1[i]
		flag = 0
	else:
		b *= list1[i]
		flag = 1
	

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

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

ret = make_divisors(int(input()))
min = 9999999999999
for i in range(int(len(ret)/2)):
    now = (ret[i*2] -1) + (ret[i*2+1] -1)
    min = now if now < min else min
    
print(min)

Submission status: Wrong Answer

Solution code:
import heapq
import math

N = int(input())

yakusuu = []

# i == 2
while N % 2 == 0:
    yakusuu.append(2)
    N = N // 2

# i >= 3
for i in range(3, int(math.sqrt(N)) + 1, 2):
    while N % i == 0:
        yakusuu.append(i)
        N = N // i

yakusuu.append(N)

yakusuu.sort()

a = 1
b = 1

for y in yakusuu:
    if a <= b:
        a *= y
    else:
        a, b = b, a
        a *= y

print(a - 1 + b - 1)

Submission status: Wrong Answer

Solution code:
n = int(input())

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


kanousei = []

yakusuu_list = make_divisors(n)

for i in yakusuu_list[:int(len(yakusuu_list)/2)]:
    if n%i==0:
        kanousei.append([i, int(n/i)])

saisyou = n + 1
index = 0
        
for i in kanousei:
    if sum(i) < saisyou:
        saisyou = sum(i)

print(saisyou-2)

Submission status: Wrong Answer

Solution code:
def yakusu(n):
        result = []
        for i in range(1,int(n**0.5)+1):
                if n % i == 0:
                        result.append(i)
                        if i != n // i:
                                result.append(n//i)
        result.sort()
        return result
yakusu = yakusu(int(input()))
m = len(yakusu)
if m % 2 ==0:
        print(yakusu[m//2-1]+yakusu[m//2+1-1]-2)
else:
        print(yakusu[m//2-1]**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

l=prime_factorize(n)
l.sort(reverse=True)
#print(l)
x=y=1

for i in l:
    if x < y:
        x=x * i
    else:
        y=y*i

#print(x,y)
print(x+y-2)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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

k = make_divisors(n)
k.sort()

ans = Max

for i in range(len(k)//2):
    if ans >= n//k[i] + k[i] - 2:
        ans = n//k[i] + k[i] - 2
        
print(ans)

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())
a=make_divisors(n)
print(a[-1]+a[-2]-2)

Submission status: Wrong Answer

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


fact = factorization(n)
fact.sort()

max_y = fact[-1][0]
ans = max_y + n // max_y - 2
print(ans)

Submission status: Wrong Answer

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

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

lst = prime_factorize(N)

if len(lst) == 1:
    print(N - 1)
else:
    a = 1
    b = 1
    if len(lst) % 2 == 0:
        for i in range(len(lst) // 2):
            a *= lst[i]
        for j in range(len(lst) // 2 , len(lst)):
            b *= lst[j]
        print(a + b - 2)
    else:
        for i in range(len(lst) // 2 + 1):
            a *= lst[i]
        for j in range(len(lst) // 2 + 1, len(lst)):
            b *= lst[j]
        print(a + b - 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
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:
abc = input()
abc_int = int(abc)
prolist = []
chk = abc_int
print(chk)
for c1 in range(chk):
    for c2 in range(chk):
        if (c1+1)*(c2+1) == abc_int:
            prolist.append(c1+c2)
print(min(prolist))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math

n = int(stdin.readline().rstrip())

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

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

li = prime_factorize(n)

a = 1
b = n

total = n+1

for i in range(len(li)):
    a *= li[i]
    b = n//a
    total = min(a+b,total)

print(total-2)

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
      for j in range(cnt) :
        arr.append(i)

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

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

  return arr

N = int(input())
fact = factorization(N)
fact.sort()


while len(fact) > 2 :
  a = fact.pop(0)
  b = fact.pop(0)
  fact.append(a*b)
  fact.sort()

if len(fact) == 1 :
  print(fact[0]-1)
else :
  print(fact[0]+fact[1]-2)

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = 10**100
for i in range(1,10**6):
  if n%i == 0:
    a = i
    b = n//i
    ans = min(ans,a-1 + b-1)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def prime(n1):
	for i in range(2, int(math.sqrt(n1))+1):
		if n1%i == 0:
			return False
	return True

n = int(input())
if prime(n):
	print(n - 1)
else:
	k = sorted(list(factors(n)))
	#print(k)
	if len(k) < 4:
		if k[1]*k[1] == n:
			print(2*k[1] - 2)
	else:
		s = k[len(k)//2 - 1] + k[len(k)//2]
		print(s - 2)

Submission status: Wrong Answer

Solution code:
N = int(input())

result = None
for i in range(1, int(N**0.5)+1):
    if N % i == 0:
        j = i + (N // i)
        if result is None or j < result:
            result = j

print(N, result - 2)

Submission status: Wrong Answer

Solution code:
import sys

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

arr = make_divisors(n)
#print(arr)
useIndex = int(len(arr)/2)
#print(useIndex)

x = arr[useIndex - 1] - 1
y = arr[useIndex] - 1
#print(x,y)
print(x + y)

Submission status: Wrong Answer

Solution code:
n = int(input())
num = 1
for i in range(1, 11):
    if n % i == 0:
        num = i
ans = int(num -1 + (n / num) -1)
print(ans)

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

list_y = make_divisors(N)
#  print(list_y)
point = len(list_y)
if point % 2 == 0:
    print(list_y[point // 2] + list_y[point // 2 - 1] - 2)
else:
    print(list_y[point // 2 + 1] + list_y[point // 2 - 1] - 2)

Submission status: Wrong Answer

Solution code:
import collections
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())
m=prime_factorize(n)
M=m[::-1]
#print(m)
if m==[n]:
    print(n-1)
else:
    a=1;b=1;c=1;d=1
    for i in m:
        if a<=b:
            a*=i
        else:
            b*=i
    #print(a,b)
    for i in M:
        if c<=d:
            c*=i
        else:
            d*=i
    #print(c,d)
    z=0
    if a+b<=c+d:
        for i in range(min(a,b)+1,max(a,b)):
            if n%i==0:
                if a+b>=i+n//i:
                    x=i;y=n//i
                    z=1
        if z==1:print(x+y-2)
        else:
            print(a+b-2)
    else:
        for i in range(min(c,d)+1,max(c,d)):
            if n%i==0:
                if c+d>=i+n//i:
                    x=i;y=n//i
                    z=1
        if z==1:print(x+y-2)
        else:
            print(c+d-2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#a, b, c, d = (int(i) for i in input().split())
#a = [int(i) for i in input().split()]


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

#print(factorization(11))

N = int(input())
nfactor = [1, 1]
nfactorindex = 0

arr = []
temp = N

#print(int(-(-N**0.5//1))+1)

for i in range(2, int(-(-N**0.5//1))+1):
    #print(nfactor)
    if temp%i==0:
        cnt= 0
        while temp%i==0:
            cnt+=1
            temp //=i
            nfactor[nfactorindex] = nfactor[nfactorindex] *i
            nfactorindex = (nfactorindex+1)%2
        arr.append([i, cnt])

if temp!=1:
    arr.append([temp, 1])
    nfactor[nfactorindex] = nfactor[nfactorindex] *temp
if arr==[]:
    arr.append([N, 1])
    nfactor[nfactorindex] = nfactor[nfactorindex] *N

#print(nfactor)

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def main(N):
    min = None
    for i in range(1, 10):
        j = N / i
        if not isinstance(j, int) and j <= 9:
            continue
        n_distance = i + j
        if min is None or n_distance < min:
            min = n_distance
    return min


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

Submission status: Wrong Answer

Solution code:
words = lambda t : list(map(t, input().split()))
n = int(input())


import math
def prime_factors(n):
    pfs = []
    m = int(math.sqrt(n)) + 1
    for num in range(2,m):
        if n % num == 0:
            while n % num == 0:
                n //= num
                pfs.append(num)
    if not n == 1:
        pfs.append(n)
    return pfs

pfs = prime_factors(n)
#print(pfs)

pfs.sort()
x = 1
y = 1
for pf in pfs:
    if x * pf + y <= y * pf + x:
        x *= pf
    else:
        y *= pf
print(x + y - 2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
fac=1
if n%2==0:
  fac=2
if n%3==0:
  fac=3
for i in range(1,166667):
  if n%(i*6-1)==0:
    fac=i*6-1
  if n%(i*6+1)==0:
    fac=i*6+1
fac+=n//fac-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())
L=make_divisors(N)
S=[]
for x in range(1,len(L)//2+1):
  S.append(L[x*2-2]+L[x*2-1])
  
print(min(S)-2)

Submission status: Wrong Answer

Solution code:
import math

n=int(input())

min=-1
for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
        j=int(n/i)
        print("divide",i,j)
        calc=j+i-2
        if min==-1 or min>calc:
            min=calc

print(min)

Submission status: Wrong Answer

Solution code:
import collections

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

import numpy as np

def main():
    n = int(input())
    tmp_ = prime_factorize(n)
    
    ans = 100000000000000

    tmp = [1]
    tmp.extend(tmp_)

    for i in range(len(tmp)-1):
        ans_tmp = np.prod(tmp[0:(i+1)]) + np.prod(tmp[i+1::])
        if ans > ans_tmp:
            ans = ans_tmp
            
    ans -= 2
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N = int(input())
m = factorize(N)

m.insert(0, 1)
l = m[0]
r = m[len(m)-1]

numL = 0
numR = len(m)-1
for i in range(len(m)):
    if numR == numL+1:
        break
    if l <= r:
        numL += 1
        l = l*m[numL]
    else:
        numR -= 1
        r = r*m[numR]

print(l+r-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = 1
b = 1
ab = 0

for i in range(2,n):
    while n % i == 0:
        if ab == 0:
            a *= i
            ab = 1
        else:
            b *= i
            ab = 0
        n //= i

print(a+b-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

arr = prime_factorize(N)
arrA = []
arrB = []

for i in range(len(arr)):
    p = arr[len(arr) - 1 - i]
    if (i + 1) % 4 == 0:
        arrA.append(p)
    elif (i + 2) % 4 == 0:
        arrB.append(p)
    elif (i + 3) % 4 == 0:
        arrB.append(p)
    elif (i + 4) % 4 == 0:
        arrA.append(p)

A = 1
B = 1
for a in arrA:
    A = A * a
for b in arrB:
    B = B * b

print(A + B - 2)

Submission status: Wrong Answer

Solution code:
import sys
import math

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


# def factorization(n):
#     factor = []
#     tmp = int(math.sqrt(n)) + 1
#     for i in range(2, tmp):
#         while n % i == 0:
#             n //= i
#             factor.append(i)
#         if len(factor) != 0:
#             factor.append(n)
#             return factor
#     return []


def solve(inputs):
    N = int(inputs[0])
    # factors = factorization(N)
    min_diff = None
    for i in range(1, 1000000):
        if N % i == 0:
            a = N // i
            diff = a + i - 2
            if min_diff is None or min_diff > diff:
                min_diff = diff
    return min_diff


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)

Submission status: Wrong Answer

Solution code:
import math
import sys

N = int(input())
a = 0

for i in reversed(range(round(math.sqrt(N)))):
  if N % (i + 1) == 0:
    print(i + N / (i + 1) - 1)
    sys.exit()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000)
INF = 1<<32


def solve(N: int):
    def primeFactorize(n: int):
        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

    l = primeFactorize(N)
    # print(l)
    l.sort()

    a = 1
    b = 1

    for i in range(len(l)):
        if(i%2 == 0):
            a *= l[i]
        else:
            b *= l[i]

    print(a+b-2)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

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)

li = []

for i in arr:
    for j in range(i[1]):
        li.append(i[0])

lengs = len(li)

mini = 0

for i in range(lengs):
    A = 1
    B = 1
    for j in range(i+1):
        A *= li[j]
    for j in range(i+1,lengs):
        B *= li[j]
    if(i == 0):
        mini = A+B
    elif(mini > A+B):
        mini = A+B
print(mini-2)

Submission status: Wrong Answer

Solution code:
def isprime(x):
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            return False
    else:
        return True

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

n = int(input())

if isprime(n):
    print(n-1)
    
else:
    lst = factorize(n)
    lst.sort(reverse = True)
    num = [1,1]
    for i in range(len(lst)):
        if num[0] == num[1]:
            num[0] *= lst[i]
        elif num[0] < num[1]:
            num[0] *= lst[i]
        else:
            num[1] *= lst[i]
    print(num[0] + num[1] - 2)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

    return arr

def main():
    n = INT()
    lis = factorization(n)
    #print(lis)
    a = 1
    b = 1
    for x in lis:
        #print(a,b)
        if x[1] % 2 == 0:
            a *= x[0] ** (x[1]//2)
            b *= x[0] ** (x[1]//2)
        else:
            if a >= b:
                a, b = b, a
            a *= x[0] ** ((x[1] + 1)//2)
            b *= x[0] ** ((x[1] - 1)//2)

    #print(a,b)
    print(a + b - 2)

if  __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

lis = []
for i in range(1,int((n**0.5) + 1)):
    if n % i == 0:
        lis.append(i)
        if i != n //i:
            lis.append(n//i)
            
lis.sort()
n2 = len(lis) // 2
a = lis[n2]
b = lis[n2 -1]
print(a-1+b-1)

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)
    return divisors
N = int(input())
if math.sqrt(N) ** 2 == N:
    print(int(2*math.sqrt(N)-2))
    exit()
arr = make_divisors(N)
print(arr[-1]+arr[-2]-2)

Submission status: Wrong Answer

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

# input
N = int(input())

# solve
def divisor(n):
    i = 1
    l = list()
    while i * i <= n:
        if n % i == 0:
            l.append(i)
            l.append(n // i)
        i += 1
    l = list(set(l))
    return l

l = sorted(divisor(N))
ans = 10 ** 12
for i in range(int(len(l) / 2)):
    ans = min(l[i] - 1 + l[len(l) - i - 1] - 1, ans)

# output
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def prime(n1):
	for i in range(2, int(math.sqrt(n1))+1):
		if n1%i == 0:
			return False
	return True

n = int(input())
if prime(n):
	print(n - 1)
else:
	k = sorted(list(factors(n)))
	#print(k)
	s = k[len(k)//2 - 1] + k[len(k)//2]
	print(s - 2)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math

n = int(stdin.readline().rstrip())
if n == 1:
    print(0)
    exit()

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

li = prime_factorize(n)

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

a = 1
b = n

total = n+1

for i in range(len(li)):
    a *= li[i]
    b = n//a
    total = min(a+b,total)

print(total-2)

Submission status: Wrong Answer

Solution code:
import sys
import math
n = int(input())
tmp = 10**12

for i in range(int(math.sqrt(n)), 2, -1):
    if n % i != 0:
        continue
    else:
        if tmp > (n//i)+(i)-2:
            tmp = (n//i)+i-2
print(tmp if tmp != 10**12 else n-1)

Submission status: Wrong Answer

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)
else:
    x = a[0]*a[1]
    y = a[-1]
    for i in range(2,m-1):
        if x<=y:
            x*=a[i]
        else:
            y*=a[i]
    print(x+y-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = n
b = 1
if n > 1000 * 1000 * 1000:
    print (n + 1)
else:
    for i in range(1,n):
        if n%i==0:
            if abs((n//i) - i) <= abs(a-b):
                a = n//i
                b = i
            else:
                break
    print(a+b-2)

Submission status: Wrong Answer

Solution code:
n=int(input())
p=1
for i in range(2,int(n**0.5)+1):
  if n%i==0:
    p=i
print(p+n/p-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())
num = prime_factorize(N)

W = []
H = []

for i in range(len(num)):
    if i % 2 == 0:
        W.append(num[i])
    else:
        H.append(num[i])

w = 1
for i in W:
    w *= i

h = 1
for j in H:
    h *= j

ans = (w-1) + (h-1)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = 1

for i in range(1,int(N**0.5)+1):
    if N % i == 0:
        ans = i

print(ans+(N/ans)-2)

Submission status: Wrong Answer

Solution code:
import collections

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

import numpy as np

def main():
    n = int(input())
    tmp_ = prime_factorize(n)
    
    ans = 100000000000000

    tmp = [1]
    tmp.extend(tmp_)

    for i in range(len(tmp)):
        ans_tmp = np.prod(tmp[0:(i+1)]) + np.prod(tmp[i+1::])
        if ans > ans_tmp:
            ans = ans_tmp
            
    ans -= 2
    print(ans)




if __name__ == '__main__':
    main()

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

prime_N = factorization(N)
A = 1
B = 1
for i in range(len(prime_N)):
    for j in range(prime_N[i][1]):
        if A <= B:
            A *= prime_N[i][0]
        else:
            B *= prime_N[i][0]

print(A + B - 2)

Submission status: Wrong Answer

Solution code:
n = int(input())


def solve(n):
    if n == 1:
        return 0
    for i in range(2, n):
        for j in range(i - 1):
            if (i - j) * (j + 1) == n:
                return i - 1


print(solve(n))