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 get_min_move(n):#素因数分解する
    a = []#素因数リスト
    one_flg = 0
    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)
    a.sort(reverse=True)
    if len(a) == 1:
        print(a[0]-1)
        return
    if(a[0] == 1):
        one_flg = 1
    while len(a) != 2:
        min1 = a.pop()
        min2 = a.pop()
        a.append(min1*min2)
        a.sort(reverse=True)
    if one_flg == 1:
        print(a[0] + a[1] -1)
    else:
        print(a[0] + a[1] -2)
    return

num = int(input())
get_min_move(num)

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 * 2 - 1)
else:
    print(n - 1)

Submission status: Wrong Answer

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

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())
s = factorization(n) 
 
s_ = []
for i in range(len(s)):
    for j in range(s[i][1]):
        s_.append(s[i][0])
a = [n]
b = [1]
c = []
 
for i in range(len(s_)):
    a.append(a[i]/s_[i])
    b.append(b[i]*s_[i])
for j in range(len(a)):
    c.append(abs(a[i]+b[i]-2))
print(int(min(c)))

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):
    if n % i == 0:
        flg = True
        break
if flg:
    print(sq * 2 - 1)
else:
    print(n - 1)

Submission status: Wrong Answer

Solution code:
def prime_factor(n):
    ass = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
 
n = int(input())
l = sorted(prime_factor(n))[::-1]
x = 1
y = 1
for i in range(len(l)):
    if x > y:
        y *= l[i]
    else:
        x *= l[i]
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[-1]+l[-2]-2)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import itertools

def prime_factor(n):
    ass = np.array([1], dtype="int64")
    for i in range(2,int(n**0.5)+1):
        while np.mod(n, i)==0:
            ass = np.append(ass, i)
            n = n // i
    if n != 1:
        ass = np.append(ass, n)
    return ass

def main():
    input = sys.stdin.readline
    N = np.int64(input())
    ass = prime_factor(N)
    num = len(ass)
    if num == 2:
        ans = ass[0] - 1 + ass[1] - 1
    else:
        ans = N
        a = np.array(list(itertools.combinations_with_replacement(np.array([True, False]), num)))
        num_a = len(a)
        for j in range(num_a//2 - 1):
            j += 1
            u = np.prod(ass[a[j]], dtype="int64")
            v = np.prod(ass[~a[j]], dtype="int64")
            ans_cand = np.int64(u - 1 + v - 1)
            if ans >= ans_cand:
                ans = ans_cand
            #print(ans_cand)

    print(ans)

if __name__ == '__main__':
    main()

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
A = sorted(factorization(N),reverse=True)
flag = True

x = 1
y = 1

for a in A:
    for i in range(a[1]):
        if x>y:
            y *= a[0]
        else:
            x *= a[0]
print(x-1 + y-1)

Submission status: Wrong Answer

Solution code:
n = int(input())

# [[素因数,数]]を出力
def fctr1(n):
    f = []
    c = 0
    r = int(n ** 0.5)
    for i in range(2, r + 2):
        while n % i == 0:
            c += 1
            n = n // i
        if c != 0:
            f.append([i, c])
            c = 0
    if n != 1:
        f.append([n, 1])
    return f


# fact = factorization(n)
fact = fctr1(n)
# fact.sort()

# max_y = fact[-1][0]
# max_y = fact[-1][0] ** fact[-1][1]
# ans = max_y + n // max_y - 2

ans = 10 ** 12

for i in range(len(fact)):
    for j in range(fact[i][1]):
        temp = fact[i][0] ** (j + 1)
        temp = temp + n // temp - 2
        ans = min(ans, temp)

print(ans)

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 = 50
s = factorization(n) 

s_ = []
for i in range(len(s)):
    for j in range(s[i][1]):
        s_.append(s[i][0])
a = [n]
b = [1]
c = []

for i in range(len(s_)):
    a.append(a[i]/s_[i])
    b.append(b[i]*s_[i])
for j in range(len(a)):
    c.append(abs(a[i]+b[i]-2))

print(int(min(c)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [1]
while not n%2:
   n//=2
   a.append(2)
i = 3
while i*i<=n:
    while not n%i:
        n//=i
        a.append(i)
    i+=2
if n>1:
    a.append(n)
c,d = 1,1
for i in range(len(a)-1,-1,-1):
    if c*a[i]<=d*a[i]:
        c*=a[i]
    else:
        d*=a[i]
print(c+d-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()

# print(fact)

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

if len(fact) == 4 :
  x = fact.pop(0) * fact.pop(-1)
  y = fact.pop(0) * fact.pop(-1)
  fact.append(x)
  fact.append(y)
elif len(fact) == 3 :
  x = fact.pop(0) * fact.pop(-1)
  fact.append(x)

# print(fact)
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 = 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

print(a + b - 2)

Submission status: Wrong Answer

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

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


def main():
    N = int(input())
    V = make_divisors(N)
    print(sum(V[len(V)//2-1:len(V)//2+1])-2)

        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
result = [0,0]
for i in range(1, int(math.sqrt(n))):
    if not n%i:
        result = [n/i,i]
print(int(sum(result)-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

d = make_divisors(N)
# print(d)

Ans_min = 1+N-2

for x in d:
  y = N/x
  Ans = x+y-2
  if Ans < Ans_min:
    Ans_min = Ans
    
print(Ans_min)

Submission status: Wrong Answer

Solution code:
import math
import itertools

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

factrist = factorization(N)

tmplist = []

# print(factrist)

a = 1
b = 1

for i in factrist:
        tmp = i[1]
        num = i[0]
        while tmp >= 2:
                a = a * num
                b = b * num
                tmp = tmp - 2
        if tmp == 1:
                tmplist.append(i[0])

sq_N = math.sqrt(N)

# print(a)
# print(b)
# print(tmplist)

sigma = 1
for i in tmplist:
        sigma *= i

L = len(tmplist)
if(L > 2):
        h_L = int(L / 2)

        ans_list = []

        List = itertools.permutations(tmplist, h_L)
        for i in List:
                ans = 1;
                for j in i:
                        ans *= j;
                ans_list.append(ans)



        sq_sigma = math.sqrt(sigma)
        ans_list.sort()

        boader = 0
        for i in range(len(ans_list)):
                if(ans_list[i] > sq_sigma):
                        boader = i
                        break

        # print(boader)
        # print(ans_list)
        # print(ans_list[boader])
        # print(ans_list[boader-1])

        print(a * ans_list[boader] + b * ans_list[boader-1] - 2)

else:
        if(L == 0):
                print(a + b -2)
        if(L == 1):
                print(a * tmplist[0] + b - 2)
        if(L == 2):
                print(a * tmplist[0] + b * tmplist[1] - 2)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
#N = pow(2,12*3)

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

plist=prime_factorize(N)
ctr=pow(2,len(plist))
minctr=N
#print(plist)
#print(ctr)
for i in range(math.ceil( math.sqrt(ctr) ) ):
    a=1
    b=1
    ctr_str=format(i,'0'+str(len(plist))+'b')
    #print(ctr_str)
    for j in range(len(ctr_str) ):
        if ctr_str[j] == '0':
            a=a*plist[j]
        else:
            b=b*plist[j]
    #print(a,b)
    minctr = min(minctr,a+b-2)

print(minctr)

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:
      x = i
      if i != n // 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 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)

sq = math.sqrt(n)

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

x = 1
y = 1
temp = 0
for i in range(len(a)):
    if x <= sq:
        x *= a[i]
        temp = i
    else:
        y *= a[i]

ans1 = x + y - 2

if i == 0:
    print(ans1)
else:
    ans2 = x / a[i - 1] + y * a[i - 1] - 2
    print(min(ans1, int(ans2)))

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 = sorted(prime_factorize(N))
#print(L)
#print(len(L))
while len(L) >= 2:
    #print(L)
    min1 = L.pop(0)
    min2 = L.pop(0)
    L.append(min1*min2)
    L=sorted(L)
if len(L)==1:
    print(sum(L)-1)
else:
    print(sum(L)-2)

Submission status: Wrong Answer

Solution code:

from sys import stdin

n = int(stdin.readline().rstrip())
ls = []

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

di = make_divisors(n)
ans = []
le = len(di)

if le%2 == 1:
    #奇数
    for i in range(1,le//2+1):
        a = di[i-1]+di[-i]
        ans.append(a)
    a = int(di[(le//2+1)])*2
    ans.append(a)
else:
    for i in range(1,le//2+1):
        a = di[i-1]+di[-i]
        ans.append(a)

print(int(min(ans)-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)
    return divisors

L = make_divisors(n)
P = []
P.append(L[-1])
P.append(L[-2])
print(sum(P)-2)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

factorize_list = factorize(n)
# print(factorize_list)
factorize_list.reverse()
a, b = 1, 1
for i in factorize_list:
    if (a < b):
        a *= i
    else:
        b *= i
# print(a, b)

print(a - 1 + b - 1)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
#N = pow(2,12*3)

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

plist=prime_factorize(N)
ctr=pow(2,len(plist))
minctr=N
#print(plist)
print(ctr)
for i in range(math.ceil( math.sqrt(ctr) ) ):
    a=1
    b=1
    ctr_str=format(i,'0'+str(len(plist))+'b')
    #print(ctr_str)
    for j in range(len(ctr_str) ):
        if ctr_str[j] == '0':
            a=a*plist[j]
        else:
            b=b*plist[j]
    #print(a,b)
    minctr = min(minctr,a+b-2)

print(minctr)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
M = int(input())

def factorization(n):  # 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])
    if arr == []: # ｎが1のとき
        arr.append([n])
    return arr

import itertools
insu = list(itertools.chain.from_iterable(factorization(M)))

if len(insu) == 1:
    print(insu[0]-1)
    exit()
while len(insu) > 2 :
    min = insu[0] * insu[1]
    insu = insu[2:]
    insu.append(min)
    insu.sort()

print(insu[0]+insu[1]-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())
l = make_divisors(n)

ans = 999999999999999999
for i in range(0, len(l)-1, 2):
  a = l[i]
  b = l[i+1]
  ans = min(ans,(a+b-2))
  
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
ans=1
for i in reversed(range(2,int(math.sqrt(n)))):
    if n%i==0 and abs(n/ans-ans)>abs(n/i-i):
        ans=n/i
            
print(int(ans-1+n/ans-1))

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

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

Submission status: Wrong Answer

Solution code:
import collections
A= 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
  
primelist=prime_factorize(A)
S = primelist[-1]
G = int(A/S)

print((G-1)+(S-1))

Submission status: Wrong Answer

Solution code:
N = int(input())

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)

A = 1
B = 1
for i in a:
  if(A > B):
    B *= i
  elif(B > A):
    A *= i
  else:
    A *= 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


a = prime_factorize(n)
if len(a) == 1:
    print(a[0] - 1)
    exit()
x = 1
y = 1
for i in range(1, len(a)+1):
    if x <= y:
        x *= a[-i]
    else:
        y *= a[-i]
ans1 = x + y - 2
x = 1
y = 1
for i in range(0, len(a)):
    if x <= y:
        x *= a[i]
    else:
        y *= a[i]
ans2 = x + y - 2
print(min(ans1, ans2))

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


p = prime_factorize(N)

ans = N + 1 - 2
tmp = [1, N]

lenP = len(p)
m = 1 << lenP

for i in range(m):
    x = 1
    y = 1
    for j in range(lenP):
        if i >> j == 0:
            x *= p[j]
        else:
            y *= p[j]
    ans = min(ans, x + y - 2)


print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#-*- coding:utf-8 -*-
n = int(input())
half = int(n/2)
print(half)
for x in range(1,half):
    for y in range(1,half):
        if n == x*y:
            print(x+y-2)
            quit()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul

N = int(input())

def main():
    primes = prime_factorize(N)
    if len(primes) == 1:
        print(primes[0] - 1)
        return
    elif len(primes) == 2:
        print(primes[0] + primes[1] - 2)
        return

    a = 1
    b = 1
    for p in reversed(primes):
        if a <= b:
            a *= p
        else:
            b *= p

    print(a + b - 2)

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

main()

Submission status: Wrong Answer

Solution code:
num_s = input()
num = int(num_s)

def check(num):
    n = []
    for i in range(1, int(num**0.5)+1):
        if i > num:
            break
        if (num % i == 0):
            n.append(i)
    return n


ans = check(num)
a = max(ans)
b = num / a

if a == 1:
    a = 1
else:
    a = a - 1
if b == 1:
    b = 1
else:
    b = b - 1

print(int(a + b))

Submission status: Wrong Answer

Solution code:
# ABC144 C
from itertools import combinations
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

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

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

    return retlist

N = ni()

ans = 0
L = []
L = factorize(N)

ans = 10**13

for i in range(1,len(L)+1):
    C = []
    C = list(combinations(L,i))
    for c in C:
        a,b = 1,0
        for j in range(len(c)):
            a *= c[j]
            b = N//a
            ans = min(ans,a-1+b-1)
            if b>a:
                break

print(ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt

n=int(input())
for i in range(int(sqrt(n)),2,-1):
  if n%i==0:
    print(i-1 + n//i-1)
    break
else:
  print(n-1)

Submission status: Wrong Answer

Solution code:
N = int(input())

def judge(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

divisors = judge(N)
divisors.sort()
while len(divisors) >= 3:
  divisors.pop(0)
  divisors.pop(-1)
print(max(1, sum(divisors)-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())

a = prime_factorize(N)
# print(a)

if len(a) == 1:
    a.append(1)
    a.sort()

while len(a) > 2:
    a1 = a.pop(0)
    a2 = a.pop(0)
    
    a.append(a1 * a2)
    a.sort()
    
# print(a)

print((a[0] - 1) + (a[1] - 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

num = int(input())
yakusu_list = make_divisors(num)
nine = [1,2,3,4,5,6,7,8,9]
yakusu_pair_list = []
a = 0
b = 0
for i, yakusu in enumerate(yakusu_list):
    
    if len(yakusu_list) % 2 == 0:
        if i % 2 == 0:
            a = yakusu
        else:
            b = yakusu
            yakusu_pair_list.append([a, b])
    else:

        if i == len(yakusu_list) -1:
            yakusu_pair_list.append([yakusu, yakusu])
    
        else:
            if i % 2 == 0:
                a = yakusu
            else:
                b = yakusu
                yakusu_pair_list.append([a, b])
best_pair = yakusu_pair_list[0]
best_move_num = best_pair[0] + best_pair[1] -2
print(yakusu_pair_list)
for yakusu_pair in yakusu_pair_list:
    this_move_num = yakusu_pair[0] + yakusu_pair[1] -2
    if this_move_num < best_move_num:
        best_pair = yakusu_pair    
        best_move_num = this_move_num
print(best_move_num)

Submission status: Wrong Answer

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

N = int(input())

N_set = prime_factor(N)

#print(N_set)

if len(N_set) == 1:
    print(N -1)
else:
    tmp = 1
    for i in range(1,len(N_set)):
        if (N**0.5 >= tmp * N_set[0]):
            tmp = tmp * N_set.pop()
        else:
            break
    print(int(tmp + N/tmp -2))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
def yinzi(n):
    list_yinzi = []
    if n <= 2:
        return list_yinzi
    for i in range(2, int(math.sqrt(n)) + 1):
        """
        为什么循环范围定在平方根呢？：因为一个数的因子是成对的，a=b*c。也就是说：找到一个因子b，肯定会找到相对应的另外一个因子c（a/b）。所以我们的工作量减少了一半。
        又有：一个因子变大，另一个因子必然要变小。假设b永远是小的那个，c是大的那个，那么b的最大值就是a的平方根。也就是b=c=(根号a)的时候。所以循环范围定在[1 , a的平方根+1]，+1的原因是为了能够取到a的平方根避免遗漏。
        """
        #如果找到了一个因子，那么把其相对应的另一个因子一同加入到因子列表中
        if n % i == 0:
            list_yinzi.extend([i, n/i])

    #此处的set为了去重，因为会出现两个相同的平方根的情况。所以去掉重复
    #sorted重排序是因为，因子都是成对成对找出来的，也就是说一次找到的两个因子肯定会有一大一小。这样把所以因子找完放在一起，大小排序就乱了
    return sorted(set(list_yinzi))
if len(yinzi(n)) == 0:
    print(n-1)
else:
    print(yinzi(n)[int(len(yinzi(n))/2)-1]+int(n/yinzi(n)[int(len(yinzi(n))/2)-1])-2)

Submission status: Wrong Answer

Solution code:
#C
import numpy as np
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())

#print(2*np.sqrt(n))

#print(factorization(n))

g = factorization(n)
f = []
for x in g:
    for y in range(1,x[1]+1):
        f.append(x[0])



if len(f) == 1:
    print(n-1)
else:
    print(int(round(2*np.sqrt(n))-1))


'''
#print(f)
f.sort()


#print(f)
dex = len(f) - 1
a = 1
b = 1
#print(dex)
while dex >= 0:
    if dex < 0:
        break
    else:
        a *= f[dex]
        dex -= 1
    if dex < 0:
        break
    else:
        b *= f[dex]
        dex -= 1

print(a+b-2)
'''

Submission status: Wrong Answer

Solution code:
n=int(input())
a = []
for i in range(1, int(n**0.5)+1):
  if n % i == 0:
    a.append(i)
    if i != n // i:
      a.append(n//i)
indx = len(a)//2
b = list(map(int,set(a)))
x = b[indx]
y = n/x
print(int((x+y)-2))

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:
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)
#print(X) #素因数
Y = []
Y.append(1)
c = 1
for j in X:
    c = c*j
    Y.append(c)
#print(Y) #約数

res = 1000000000000
for i in Y:
    b = int(N/i)
    if res > i + b:
        res = i + b

print(res-2)

Submission status: Wrong Answer

Solution code:
import math
import itertools

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

factrist = factorization(N)

tmplist = []

# print(factrist)

a = 1
b = 1

for i in factrist:
        tmp = i[1]
        num = i[0]
        while tmp >= 2:
                a = a * num
                b = b * num
                tmp = tmp - 2
        if tmp == 1:
                tmplist.append(i[0])

sq_N = math.sqrt(N)

# print(a)
# print(b)
# print(tmplist)

sigma = 1
for i in tmplist:
        sigma *= i

L = len(tmplist)
if(L > 2):
        h_L = int(L / 2)

        ans_list = []

        List = itertools.permutations(tmplist, h_L)
        for i in List:
                ans = 1;
                for j in i:
                        ans *= j;
                ans_list.append(ans)



        sq_sigma = math.sqrt(sigma)
        ans_list.sort()

        boader = 0
        for i in range(len(ans_list)):
                if(ans_list[i] > sq_sigma):
                        boader = i
                        break

        # print(boader)
        # print(ans_list)
        # print(ans_list[boader])
        # print(ans_list[boader-1])

        print(a * ans_list[boader] + b * ans_list[boader-1] - 2)

else:
        if(L == 1):
                print(a * tmplist[0] + b - 2)
        if(L == 2):
                print(a * tmplist[0] + b * tmplist[1] - 2)

Submission status: Wrong Answer

Solution code:
import heapq
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 not arr:
        arr.append([n, 1])
    return arr


A = factorization(N)
if len(A) == 1:
    print(A[0][0]-1)
else:
    x = []
    for i in range(len(A)):
        for _ in range(A[i][1]):
            x.append(-A[i][0])
    heapq.heapify(x)
    print(x)
    while len(x) > 2:
        a = heapq.heappop(x)
        b = heapq.heappop(x)
        c = heapq.heappop(x)
        heapq.heappush(x, a)
        heapq.heappush(x, -b*c)
    print(x)
    d = -heapq.heappop(x)
    e = -heapq.heappop(x)
    print(d+e-2)