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

input_num = int(input())
factors = prime_factorize(input_num)

if len(factors) == 1:
    print(input_num - 1)
elif len(factors) > 2:
    while len(factors) != 2:
        tmp = factors
        tmp[0] = tmp[0] * tmp[1]
        tmp.pop(1)
        factors = sorted(tmp)
    
    print(factors[0] -1 + factors[1] - 1)
    
else:
    print(factors[0] -1 + factors[1] - 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
min = n
if n % 2 == 0:
    k = n/2 + 1
else:
    k = (n+1)/2 
for x in range(1,int((n+1)/2)):
    if n % x == 0:
        if min > ((x-1) + (n/x - 1)):
            min = ((x-1) + (n/x - 1))
print(int(min))

Submission status: Wrong Answer

Solution code:
n = int(input())
x = 1
y = 1
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)

for i in a:
    if x <= y:
        x *= i
    else:
        y *= i
print((x-1)+(y-1))

Submission status: Wrong Answer

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

sosu_dict = {}
a = N
b = N
#print(int(math.sqrt(N+1)))
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 ** 13 +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:
import math
import sys
N=int(input())
Nsq=math.sqrt(N)
ans=1
anans=1
for i in range(1,int(Nsq)+1):
    if N%i==0:
        ans=max(ans,i)
for j in range(int(Nsq)+1,N):
    if N%j==0:
        anans=j
        break
print(max(ans+int(N/ans)-2,anans+int(N/anans)-2))

Submission status: Wrong Answer

Solution code:
import sys

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

Nlist = factorization(N)
l = 1
m = 10**12 + 1
for n in Nlist:
    for i in range(1, n[1]+1):
        l *= n[0]*i
        if m > int((l - 1) + (N/l - 1)):
            m = int((l - 1) + (N/l - 1))
print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())

lcd = []

while n % 2 == 0:
    lcd.append(2)
    n //= 2

f = 3
while f * f <= n:
    if n % f == 0:
        lcd.append(f)
        n //= f
    else:
        f += 2
if n != 1:
    lcd.append(n)

lcd.sort()

# print(lcd)

j = len(lcd) - 1

ansi = 1
ansj = lcd[-1]

for k in range(j):
    if ansi > ansj:  # * lcd[k]
        ansj *= lcd[k]
    else:
        ansi *= lcd[k]

ansk = 1
ansl = lcd[-1]

for k in range(j):
    if ansk * lcd[k] > ansl:
        ansl *= lcd[k]
    else:
        ansk *= lcd[k]

print(min(max(ansi-1, 0)+max(ansj-1, 0), max(ansk-1, 0)+max(ansl-1, 0)))

Submission status: Wrong Answer

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

answer=[]
m=math.floor(N**0.5)+1
for i in range(1,m):
    if N % i == 0:
        answer.append(i+N/i)
        
print(min(answer)-2)

Submission status: Wrong Answer

Solution code:
import sys

#+++++

def sp(value):
		ret_v=[]
		v=value
		for i in range(2, value):
			if v % i == 0:
				ret_v.append(i)
				v=v//i
				
				while v % i == 0:
					ret_v.append(i)
					v=v//i
					
			if i*i>v:
				ret_v.append(v)
				return (ret_v)
				
		ret_v.append(v)
		return (ret_v)

def main():
	a = int(input())
	bb=sp(a)
	ag=1
	bg=1
	for i,v in enumerate(bb):
		if i % 2 == 0:
			ag=ag*v
		else:
			bg=bg*v

	print(ag+bg-2)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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

result = 10 ** 12

tmp = make_divisors(n)

for i in range(len(tmp) // 2):

   num0 = tmp[i]
   num1 = tmp[len(tmp) - i - 1]

   num_add = num0 + num1
   if num_add < result:
      result = num_add

print(str(result - 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())
lst = prime_factorize(n)

if len(lst)==1:
    print(n-1)
    
else:
    num = [1,1]
    lst.sort(reverse = True)
    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]
    num2 = [1,1]
    lst.sort()
    for i in range(len(lst)):
        if num2[0] == num2[1]:
            num2[0] *= lst[i]
        elif num2[0] < num2[1]:
            num2[0] *= lst[i]
        else:
            num2[1] *= lst[i]
    print(min((num[0]+num[1]) , (num2[0]+num2[1])) -2)

Submission status: Wrong Answer

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

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

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

    return arr

n = int(input())
p = factorizeFlat(n)
p.sort()
#p = p[::-1]
t = (n**0.5)//1
a = 1
b = 1
for x in p:
    #print("a:{} b:{} t:{}".format(a, b, t))
    if a * x < t:
        a = a * x
    else:
        if a * x > b * x:
            b = b * x
        else:
            a = a * x
#print("a:{} b:{}".format(a, b))
print(a - 1 + b - 1)

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=arr[0]
   b=arr[-1]
   # ss=0
   s=0
   # print(arr,len(arr))
   for i in range(len(arr)-2):
      if len(arr)==2:
         a=arr[0]
         b=arr[-1]
      else:
         if a <= b:  
            a = a * arr[i+1]
            # print(a)
         else:
            b = b * arr[i+1]

   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 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())
P = [1]
for i, j in factorization(n):
    for _ in range(j):
        P.append(i)
ans = 9999999999999
for p in P:
    a = p
    b = n // p
    tmp = (a-1) + (b-1)
    if tmp < ans:
        ans = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
for i in range (1, 10**12):
    if n <= i**2:
        m = i
        break

for i in range(0,m//2+1):
    for j in range(0,m//2+1):
        if (m-i-j)*(m+i) == n:
            print(m-i-j+m+i-2)
            break

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)
    l.sort()

    a = 1
    b = 1

    for i in range(len(l)-1,-1,-1):
        if a <= b:
            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:
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

n = sorted(make_divisors(N))

sum_yakusuu = N
for _n in n:
    if _n == 1:
        continue
    if _n+N/_n < sum_yakusuu:
        sum_yakusuu = int(_n+N/_n)
    else:
        print(int(_n+N/_n-2))
        break

Submission status: Wrong Answer

Solution code:
n = int(input())
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.append((i-1)+(n//i)-1)
print(min(divisors))

Submission status: Wrong Answer

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

x = prime_factorize(n)
omi = 1
oma = 1
for i in x:
    omi_c = min(omi,oma)
    oma_c = max(omi,oma)
    omi_c = omi_c * i
    omi = omi_c
    oma = oma_c

print(omi + oma - 2)

Submission status: Wrong Answer

Solution code:
import math

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

l = factorization(n)

x = 1
y = n
ans = []

for i in range(len(l)):
	for j in range(l[i][1]):
		x *= l[i][0]
		y /= l[i][0]
		ans.append(x+y)
ans1 = int((min(ans)-2))

x = 1
y = 1
flag=1
for i in range(len(l)):
	if l[i][1] % 2 == 0:
		x *= l[i][0] ** (l[i][1] // 2)
		y *= l[i][0] ** (l[i][1] // 2)
	else:
		num = int(l[i][1] / 2)
		if flag == 1:
			x *= l[i][0] ** num
			y *= l[i][0] ** (l[i][1]-num)
			flag = -1
		elif flag == -1:
			y *= l[i][0] ** num
			x *= l[i][0] ** (l[i][1]-num)
			flag = 1

ans2 = x+y-2

print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import math

def make_divisors(n):
  divisors = []
  for i in range(1, int(math.sqrt(n))+1):
    if n % i == 0:
      print(i)
      x = i
      y = n // i
      divisors.append([x, y])

  return divisors

def list_sum(t_list):
  return t_list[0] + t_list[1]

n = int(input())
yakusu = make_divisors(n)

data = list(map(list_sum, yakusu))
print(min(data) - 2)

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)-1):
  a = l[i]
  b = l[i+1]
  if a * b == n:
    ans = min(ans, (a+b-2))

  if a * a == n:
    ans = min(ans, (a+a-2))

  if b * b == n:
    ans = min(ans, (b+b-2))

print(ans)

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=arr[0]
   b=arr[-1]
   # ss=0
   s=0
   # print(arr,len(arr))
   for i in range(len(arr)-2):
      if len(arr)==2:
         a=arr[0]
         b=arr[-1]
      else:
         if a < b:  
            a = a * arr[i+1]
            # print(a)
         else:
            b = b * arr[i+1]

   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:
import math
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
rn=math.sqrt(n)

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())

def prime_factorize(n):
    a = []
    time = 0
    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)
        a.append(1)
    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

a=int(input())
x=(math.ceil(a/2))
for i in range(x+1):
 if a%(x-i+1)==0:
  print(int(x-i-1+(a/(x-i+1))))
  break

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

def f2(n):
    N = n
    a = []
    while n % 2 == 0:
        # a.append(2)
        a.append([abs(N//2-2), N//2, 2])
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
        #     a.append(f)
            a.append([abs(N//f-f), N//f, f])
            n //= f
        else:
            f += 2
    if n != 1:
        # a.append(n)

        # print("---------")
        # print("0:"+str(abs(tmpN-n)))
        # print("1:"+str(tmpN))
        # print("2:"+str(n))
        a.append([abs(N//n-n), N//n, n])
    return a

n = int(input())
# print(prime_factorize(n))

ans = f2(n)
ans.sort()
# print(ans)
if len(ans) == 1:
        print(n-1)
else:
        print(ans[0][1] + ans[0][2] - 2)
# for i in range(len(ans)):
#         if ans[i][1]*ans[i][2] == n:
#                 print(ans[i][1] + ans[i][2] - 2)
#                 exit()

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = N

for i in range(round(math.sqrt(N))):
  j = i + 1
  if N % j == 0:
    if a > j + N / j:
      a = j + N / j
print(a - 2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())

n = N / 2

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

judge = 1
c = factorize(N)
for i in range(len(c)):
  d = c[i]
  for k in range(i+1, len(c)):
    temp = d * c[k]
    if temp > n :
      break
    if abs(n/2 - temp) < (n/2 -judge):
      judge = temp


ans = int((judge + (N / judge) -2))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

n = int(input())


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


list_ = abc(n)
# print(list_)
list_.sort()
tmp = sum(list_)//2
N = len(list_)
#print(list_)
dp = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(N):
    for j in range(1,N):
        if i == j:
            continue
        else:
            if dp[i][j-1] + list_[j] < tmp:
                dp[i][j] = dp[i][j-1] + list_[j]

            elif dp[i][j-1] + list_[j] == tmp:
                print((tmp-1)*2)
                sys.exit()
            else:
                continue
tmplist = list(itertools.chain.from_iterable(dp))
def getNearestValue(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]
#print(tmplist,tmp)
#tmplist.sort()
#tmp1 = getNearestValue(tmplist,tmp)
tmp1 = max(tmplist)
if tmp1 == 0:
  print(n-1)
  sys.exit()
#print(tmplist,tmp1,tmp)
print((tmp1 - 1)+(n//tmp1-1))

Submission status: Wrong Answer

Solution code:
import sys

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

Nlist = factorization(N)
l = 1
if len(Nlist) == 2:
    if Nlist[0][1] == 1 and Nlist[1][1] == 1:
        print(int(Nlist[0][0] + Nlist[1][0] - 2))
        sys.exit()

for n in Nlist:
    for i in range(1, n[1]+1):
        l *= n[0]*i
        if l >= N/l:    
            print(int((l - 1) + (N/l - 1)))
            sys.exit()

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

n = sorted(make_divisors(N))

sum_yakusuu = N
for _n in n:
    if _n == 1:
        continue
    if _n+N/_n < sum_yakusuu:
        sum_yakusuu = _n+N/_n
    else:
        print(int(_n+N/_n-2))
        break

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)
print(l)
ans = n-1
for i in range(0, len(l)-1):
  a = l[i]
  b = l[i+1]
  if a * b == n:
    ans = min(ans, (a+b-2))

  if a * a == n:
    ans = min(ans, (a+a-2))

  if b * b == n:
    ans = min(ans, (b+b-2))


print(ans)

Submission status: Wrong Answer

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

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

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

a = factorize(n)
m = len(a)
ans = 0
if m==1:
    print(a[0]-1)
elif m==2:
    print(a[0]+a[1]-2)
elif m==3:
    z = a[0]*a[1]
    print(z+a[2]-2)
else:
    b = make_divisors(n)
    k = len(b)
    b.sort()
    ans = 10*12
    for i in range(k//2):
        ans = min(ans,b[i]+b[k-1-i]-2)
    print(ans)

Submission status: Wrong Answer

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

import itertools

import numpy as np

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

    primes = prime_factorize(n)


    def list_difference(list1, list2):
        result = list1[:]
        for value in list2:
            if value in result:
                result.remove(value)

        return result

    c = -1

    if len(primes) == 1:
        print(n - 1)
    else:
        for i in range(1, len(primes)):
            li = list(map(list, set(list(itertools.combinations(primes,i)))))
            for l in li:
                l2 = list_difference(primes, l)
                x = np.prod(l)
                y = np.prod(l2)
                num = x + y - 2
                print(num)

                if c == -1:
                    c = num
                elif c > num:
                    c = num

        print(c)


if __name__ == '__main__':
    main()

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
ans=prime_factorize(n)

while len(ans)>=3:
    ans.append(ans[0]*ans[1])
    ans[0:2]=[]
    
    ans.sort()
    
    

if len(ans)==1:
    count=ans[0]-1
else:
    count=ans[0]-1+ans[1]-1

print(count)

Submission status: Wrong Answer

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

sosu_dict = {}
a = N
b = N
#print(int(math.sqrt(N+1)))
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 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
    a.append(n)
    return a

N = int(input())
a = prime_factorize(N)
a.append(1)
res = float('inf')
for x in a:
    t = int(N/x)
    res = min(res, x+t)
print(res-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

def f2(n):
    N = n
    a = []
    while n % 2 == 0:
        # a.append(2)
        a.append([abs(N//2-2), N//2, 2])
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
        #     a.append(f)
            a.append([abs(N//f-f), N//f, f])
            n //= f
        else:
            f += 2
    if n != 1:
        # a.append(n)

        # print("---------")
        # print("0:"+str(abs(tmpN-n)))
        # print("1:"+str(tmpN))
        # print("2:"+str(n))
        a.append([abs(N-n), N, n])
    return a

n = int(input())
# print(prime_factorize(n))

ans = f2(n)
ans.sort()
print(ans)
if len(ans) == 1:
        print(n-1)
else:
        print(ans[0][1] + ans[0][2] - 2)
# for i in range(len(ans)):
#         if ans[i][1]*ans[i][2] == n:
#                 print(ans[i][1] + ans[i][2] - 2)
#                 exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np


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


def solve(N: int):

    fct_list = prime_factorize(N)

    result = 1e12

    if len(fct_list) == 2:
        x = fct_list[0]
        y = fct_list[1]

        print(x - 1 + y - 1)
    elif len(fct_list) == 1:
        x = fct_list[0]
        print(x - 1)
    elif len(fct_list) == 0:
        print(0)

    else:
        for i in range(1, len(fct_list) - 1):

            x = np.prod(fct_list[: i + 1])
            y = np.prod(fct_list[i + 1 :])

            result = min(result, x - 1 + y - 1)
        print(result)
    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 pf(n:int):
    r = []
    while n%2==0:
        r.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            r.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        r.append(n)
    return r

n = int(input())
x = pf(n)

if len(x)==1:
    print(x[0]-1)
else:
    import itertools
    
    bits = list(itertools.product([0,1], repeat=len(x)))
    mini = 10*12
    mini_idx = 0

    for idx, bit in enumerate(bits):
        nbit = []
        for i in bit:
            if i==0:
                nbit.append(1)
            else:
                nbit.append(0)
                
        res = 1
        for j in range(len(x)):
            if bit[j]==1:
                res *= x[j]
        resn = 1
        for j in range(len(x)):
            if nbit[j]==1:
                resn *= x[j]
        res = abs(res - resn)

        if res < mini:
            mini = res
            mini_idx = idx

    bit = bits[mini_idx]
    nbit = []
    for i in bit:
        if i==0:
            nbit.append(1)
        else:
            nbit.append(0)

    res = 1
    for j in range(len(x)):
        if bit[j]==1:
            res *= x[j]
    resn = 1
    for j in range(len(x)):
        if nbit[j]==1:
            resn *= x[j]

    print(res+resn-2)

Submission status: Wrong Answer

Solution code:
import numpy as np
nm_min = 9999999999999
n = int(input())
for i in range(n):
  if n%(1+i)==0:
    m=n/(i+1)
    nm = m+(i+1)
    if nm_min>nm:
      nm_min=nm
print(nm_min-2)

Submission status: Wrong Answer

Solution code:
def test():
    n = int(input())
    f = 3
    a = [1,1]
    while n % 2 == 0:
        b = min(a)
        a[a.index(min(a))] += b*2 - b
        n //= 2

    while f*f <= n:
        if n % f == 0:
            b = min(a)
            a[a.index(min(a))] += b*f - b
            n //= f
        else:
            f += 2
    if n != 1:
        b = min(a)
        a[a.index(min(a))] += b * n - b

    print(sum(a)-2)


if __name__ == "__main__":
    test()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

def prime_factorize(n):
    a = []
    time = 0
    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 len(a) == 0 and time == 0:
        a.append(1)
        time = 1
    if n != 1:
        a.append(n)
    return a

print(prime_factorize(N))

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:
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=arr[0]
   b=1
   # ss=0
   s=0
   # print(arr)
   for i in range(len(arr)-1):
      if len(arr)==2:
         a=arr[0]
         b=arr[-1]
         
      else:
         if a < b:  
            a = a * arr[i+1]
            # print(a)
         else:
            b = b * 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 i < 10 and n % i == 0:
                divisors.append([i, n//i])
            # if i != n // i:
            #     divisors.append(n//i)

    # divisors.sort()
    return divisors


N = int(input())

div = make_divisors(N)
div2 = []

for i in div:
    div2.append(abs(i[0]-i[1]))

idx = div2.index(min(div2))

print((div[idx][0]-1) + (div[idx][1]-1))