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:
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 divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def factorize2(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

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:
    fct = factorize2(n)
    b = list( num(div) for div in divisorize(fct))
    k = len(b)
    ans = 10**12 +1
    for i in range(k):
        for j in range(i+1,k):
            if b[i]*b[j]==n:
                ans = min(ans, b[i]+b[j]-2)
                break
            else:
                continue
    print(ans)

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)

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

Submission status: Wrong Answer

Solution code:
pf = []
m = int(input())
tmp = 0
for i in range(2, int(m ** 0.5) + 1):
	while m % i == 0:
		pf.append(i)
		m //= i
if m > 1:
	pf.append(m)
L = len(pf)
if L == 1:
	print(pf[0]-1)
elif L == 2:
	print(pf[0] + pf[1] - 2)
else:
	maxva = 1
	count=0
	while(count<L-2):
		for i in range(count, L-1):
			maxva = maxva * pf[i]
		M = pf[L-1]
		if maxva/M > M:
			pf[L-1] = M*pf[count]
		else:
			pf[L-2] *= pf[count]
		count += 1
	sum = pf[L-1] + pf[L-2] - 2
	print(sum)

Submission status: Wrong Answer

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

n = int(input())

cnt = 0
i = 2
a = prime_factorize(n)
if len(a) == 1:
    a.append(1)
b = []
for i in range(1,len(a) // 2 + 2):
    b.append(list(itertools.combinations(a, i)))

m = 10**12
for i in range(len(b)):
    if i > 0:
        if b[i] != b[i-1]:
            for j in range(len(b[i])):
                c = np.prod(b[i][j])
                d = n // c
                if m > c+d:
                    m=c+d

print(m-2)

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:
horizontal = 1

N = int(input())

loop = int(N/2)
for i in range(2, loop):
    if (N % (loop - i) == 0):
        horizontal = loop - i
        break

print(horizontal + int(N / horizontal))

Submission status: Wrong Answer

Solution code:

N = int(input())

factor = []

tmp = int(N**0.5) + 1
for num in range(2,tmp):
    while N % num == 0:
        N //= num
        factor.append(num)

if N == 1:
    factor.append(N)

    A=1
    B=1
    for i in range(len(factor)):
        if i % 2 == 0:
            A *= factor[i]
        else:
            B *= factor[i]

    print(A+B-2)

else:
    A=1
    B=1
    for i in range(len(factor)):
        if i % 2 == 0:
            A *= factor[i]
        else:
            B *= factor[i]
    
    if A * B < N:
        print(A*B + N -2)
    elif A > B:
        print(A + B* N -2)
    else:
        print(A*N + 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 * pf:
        x *= pf
    else:
        y *= pf
print(x + y - 2)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
a = N
b = round(math.sqrt(N))

for i in range(b):
  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

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

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    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 = sorted(prime_factorize(n), reverse = True)
#print(x)
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)

print(omi + oma - 2)

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 divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def factorize2(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

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:
    fct = factorize2(n)
    b = list( num(div) for div in divisorize(fct))
    k = len(b)
    ans = 10**12 +1
    for i in range(k-1):
        for j in range(i+1,k):
            if b[i]*b[j]==n:
                ans = min(ans, b[i]+b[j]-2)
                break
            else:
                continue
    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import functools
import operator
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

# def prod_dfs(a, p, n):
#     # print(a, p)
#     if p * n >= sqr:
#         # print(a, p, n, sqr)
#         return p
#     tmp = 0
#     prev = 0
#     for i, next_ in enumerate(a):
#         if prev == next_:
#             continue
#         prev = next_
#         tmp = max(prod_dfs(a[:i] + a[i+1:], p * n, next_), tmp)
#     return tmp

# def prod_dfs_(a):
#     tmp = 0
#     prev = 0
#     for i, next_ in enumerate(a):
#         if prev == next_:
#             continue
#         prev = next_
#         tmp = max(prod_dfs(a[:i] + a[i+1:], 1, next_), tmp)
#     return tmp

# prod = functools.partial(functools.reduce, operator.mul)

a = prime_factorize(N)
sqr = math.sqrt(N)

if len(a) == 1:
    print(N - 1)
elif len(a) == 2:
    print(a[0] + a[1] - 2)
else:
    ans = 10 * 6
    for i in range(2 ** len(a)):
        tmp = 1
        for j in range(len(a)):
            if ((i >> j) & 1):
                tmp *= a[j]
        if abs(ans) > abs(sqr - tmp):
            ans = tmp - sqr

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

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 = np.sqrt(n)
N = len(list_)
#print(list_)
dp = [[1 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]
            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:
#!/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]
        y = 1
        print(x - 1 + y - 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(int(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:
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]
        if m > int((l - 1) + (N/l - 1)):
            m = int((l - 1) + (N/l - 1))
print(m)

Submission status: Wrong Answer

Solution code:
import fractions
A = int(input())
for i in range(2,A+1):
  a = fractions.gcd(A,i)
  b = A/a
  break
print(int(i + b -2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#
# Author:   bebebe
# Created:  2019-10-27
#

import math

def divisor(M):
    maxX = int(math.sqrt(M))
    for x in range(2, maxX + 2):
        if M % x == 0:
            return x, M // x
    return 1, M


N = int(input().strip())
N_sqrt = int(math.sqrt(N))

M = N
divi_list = []
while True:
    d1, d2 = divisor(M)
    if d1 == 1:
        divi_list.append(d2)
        break
    else:
        divi_list.append(d1)
        M = d2

a = 1
b = 1
for x in divi_list[::-1]:
    if a < b:
        a *= x
    else:
        b *= x

print(a + b - 2)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

   # 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]
         else:
            b = b * arr[i-1]

   # print("a,b:",a,b)
   return (b-1)+(a-1)
   # return [a,b]


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

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

    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]
        y = 1
        print(x - 1 + y - 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(int(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:
import sys
import math
ab = []
abc= []
k = 0
def divisor(n):
    global k
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ab.append(i)
            k=k+1
            if i**2 == n:
                continue
            abc.append(n//i)
a = input()
a = int(a)
divisor(a)
#print(ab)
#print(abc)
print(ab[-1]+abc[-1]-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=arr[-1]

   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]
         else:
            b = b * arr[i-1]

   print("a,b:",a,b)
   return (b-1)+(a-1)
   # return [a,b]


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

Submission status: Wrong Answer

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


if math.sqrt(N).is_integer():
    print(int(math.sqrt(N) * 2 - 2)) 
    exit()


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

print(fct)



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


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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
 
answer=[]
m=math.ceil(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 math

N = int(input())
a = N
b = round(math.sqrt(N))

for i in range(b):
  for j in range(b):
    if (i + 1) * (j + 1) == N:
      if a > (i + 1) * (j + 1):
        a = i + j
print(a)

Submission status: Wrong Answer

Solution code:
import math
N = int(input()) 
factor = []
tmp = int(math.sqrt(N)) + 1
list = range(2,tmp)
for num in list[::-1]:
    while N % num == 0:
        N //= num
        factor.append(num)
        factor.append(N)
    if not factor:
        factor.append(N)
        factor.append(0)
    else:
        pass
    break
f=sum(factor)-1
print(f)

Submission status: Wrong Answer

Solution code:
import numpy as np
num=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

fact_arr=np.array(prime_factorize(num))
def GetDoubleFact(arr):
    _min=np.min(arr)
    arr=np.delete(arr,arr.argmin())
    sec_min=np.min(arr)
    arr=np.delete(arr,arr.argmin())
    arr=np.append(arr,_min*sec_min)
    print(arr)
    return arr
print(fact_arr)
if len(fact_arr)==1:
    print(fact_arr[0]-1)
else:
    while len(fact_arr)>2:
        fact_arr=GetDoubleFact(fact_arr)
    print(fact_arr[0]+fact_arr[1]-2)

Submission status: Wrong Answer

Solution code:

N = int(input())

factor = []

tmp = int(N**0.5) + 1
for num in range(2,tmp):
    while N % num == 0:
        N //= num
        factor.append(num)

if N == 1:
    factor.append(N)
    print(factor)

    A=1
    B=1
    for i in range(len(factor)):
        if i % 2 == 0:
            A *= factor[i]
        else:
            B *= factor[i]

    print(A+B-2)

else:
    A=1
    B=1
    for i in range(len(factor)):
        if i % 2 == 0:
            A *= factor[i]
        else:
            B *= factor[i]
    
    if A * B < N:
        print(A*B + N -2)
    elif A > B:
        print(A + B* N -2)
    else:
        print(A*N + B -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 = []
    cnt=0
    while n % 2 == 0:
        cnt+=1
        # a.append(2)
        a.append([abs(N//(2**cnt)-(2**cnt)), N//(2**cnt), 2**cnt])
        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)
        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:
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()
else:print(int(M / insu[-1] + insu[-1] -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)
    ans = 0
    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 = 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 prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
def prod(n):
  result = 1
  for x in n:
    result *= x
  return result
  
a = prime_factorize(n)
b = [a.pop(-1)]

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

try:
  if prev_result < prod(a) + prod(b):
    a.append(b.pop(b.index(min(b))))

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

Submission status: Wrong Answer

Solution code:
import sys
import math

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

n = int(input())
ans = n
if is_prime(n) == True:
	print(n - 1)
else:
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if i * j == n:
				if ans > i + j:
					ans = (i - 1) + (j - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
M=N
tmp=0
temp=0
li=[]
while N%2==0:
    li.append(2)
    N//=2
waru=3
while waru*waru<=N:
    if N%waru==0:
        li.append(waru)
        N//=waru
    else:
        waru+=2
if len(li)==0:
    print(N-1)
else:
    for i in range(M//2,1,-1):
        #print(M,i,temp,tmp)
        if M%i==0:
            temp=i
            if temp*temp==M:
                temp=tmp
                break
            elif tmp*temp==M:
                break
            else:
                tmp=temp
                #print("Yes")
        #print(i,temp,tmp)
    print(temp+tmp-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)

if len(serch_mini) > 1:
    serch_mini.remove(serch_mini[-1])

print(min(serch_mini)-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 = 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))

print(ans)

Submission status: Wrong Answer

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

def mk_factor(num):
    factor = 2
    factor_list = []

    while num > 1 and factor < int(math.sqrt(num))+1:
        if num % factor == 0:
            factor_list.append(factor)
            num //= factor
        else:
            factor += 1

    factor_list.append(num)

    return factor_list

def nearest_path(factor_list):
    if len(factor_list) == 1:
        return [0, factor_list[0]-1]
    else:
        len_fac = len(factor_list)
        move_i_list = [factor_list[i] for i in range(len_fac) if i % 2 == 0 ]
        move_i = 1
        for i in move_i_list:
            move_i *= i

        move_j_list = [factor_list[i] for i in range(len_fac) if i % 2 == 1 ]
        move_j = 1
        for j in move_j_list:
            move_j *= j

    return [move_i -1, move_j -1]

factor_list = mk_factor(num)
# print(factor_list)
print(sum(nearest_path(factor_list)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
N = int(input())

first_num = 0
second_num = 0
min_diff = N
for i in range(1, N // 2):
    now_diff = abs(N // i - i)
    if N % i == 0 and min_diff > now_diff:
        first_num = i
        second_num = N // i
        min_diff = now_diff
print(max(first_num + second_num - 2, 0))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
res = float('inf')
for n in range(1, int(np.sqrt(N))):
    if N % n == 0:
        t = N/n
        res = int(min(res, n+t))
print(res-2)

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

print(min(div2))

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):
        tmp_1 = 1
        tmp_2 = 1
        for k in tmp[0:(i+1)]:
            tmp_1 *= k
        for l in tmp[i+1::]:
            tmp_2 *= l
        #ans_tmp = np.prod(np.array(tmp[0:(i+1)])) + np.prod(np.array(tmp[i+1::]))
        ans_tmp = tmp_1 + tmp_2
        if ans > ans_tmp:
            ans = ans_tmp
            
    ans -= 2
    print(int(ans))




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)
    a.sort(reverse = True)
    return a

a = prime_factorize(n = N)
print(sum(a) + 1)

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

    a1 = 1
    b1 = 1
    a2 = 1
    b2 = 1

    for i in range(len(l)-1,-1,-1):
        if a1 <= b1:
            a1 *= l[i]
        else:
            b1 *= l[i]

    for i in range(len(l)):
        if a2 <= b2:
            a2 *= l[i]
        else:
            b2 *= l[i]
    if abs(b1-a1) < abs(b2-a2):
        print(a1+b1-2)
    else:
        print(a2+b2-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:
from math import sqrt
n = int(input())
n1 = n
a = []
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)
if len(a)>2:
    if sqrt(n1)-int(sqrt(n1))>0:
        print(2*int(sqrt(n1)+0.5)-1)
    else:
        print(int(2*sqrt(n1))-2)
else:
    res=0
    for i in a:
        res+=i-1
    print(res)

Submission status: Wrong Answer

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