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:
c=int(input())
count=1
ans=10000000000000
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
      if n%i==0:
          n = int(n/i)
          table.append(i)
      i += 1
  if n > 1:
    table.append(n)
  return table
d=list(prime_decomposition(c))
for k in range(len(d)):
    count*=d[k]
    c=int(c/d[k])
    if ans>count+c:
        ans=count+c
print(ans-2)

Submission status: Wrong Answer

Solution code:
import itertools
import functools
import operator
import math
from bisect import bisect_right as br
from bisect import insort_right as ir

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.ceil(math.sqrt(N))
sqr = math.sqrt(N)

if len(a) == 1:
    print(N - 1)
elif len(a) == 2:
    print(a[0] + a[1] - 2)
else:
    p = prod_dfs_(a)
    print(N // p + p - 2)

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)
            
aaa = 0
bbb = 10**12+1
j = 0

for i in range(1,len(divisors)//2+1):
    aaa = divisors[j]+divisors[j+1]-2
    if aaa < bbb:
        bbb = aaa
    j += 2
    
print(bbb)

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 ** 9

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 is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

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 is_prime(n) == True:
    print(n-1)
else:
    ls = (make_divisors(n))
    print(ls[-1]+ls[-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 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 = np.int64(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())
for i in reversed(range(1,int(N**0.5))):
    if N % i == 0:
        print(int(i+N//i-2))
        break

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

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

target_list = factorize(int(input()))
loop=len(target_list)+1
target_len=len(target_list)
ans=1000000000000

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

print(ans)

Submission status: Wrong Answer

Solution code:
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)
            
aaa = 0
bbb = 10**12+1
j = 0

for i in range(1,len(divisors)//2+1):
    aaa = divisors[j]+divisors[j+1]-2
    print(aaa)
    if aaa < bbb:
        bbb = aaa
    j += 2
    
print(bbb)

Submission status: Wrong Answer

Solution code:
N = int(input())
import numpy as np

a = np.floor(np.sqrt(N))
while True:
  if N%a==0:
    break
  N=N-1
b=N/a
print(int(a+b-2))

Submission status: Wrong Answer

Solution code:
import itertools
import numpy

def prime(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())
lis = prime(N)

diff = 10**9
a, b = 0, 0
ans = -1
for i in itertools.permutations(lis):
    for j in range(1,len(i)):
        if diff > abs(sum(i[:j])-sum(i[j:])):
            ans = numpy.prod(i[:j]) + numpy.prod(i[j:]) - 2
        diff = min(diff, abs(sum(i[:j])-sum(i[j:])))
if ans == -1:
    print(N-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
a=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
list=[]
list=make_divisors(a)
#print(math.floor(len(list)/2)-1)
#print(math.floor(len(list)/2))
print(list[math.floor(len(list)/2)-1]-1+list[math.floor(len(list)/2)]-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 = prime_factor(n)
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:
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)
    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:
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())
d = make_divisors(n)
a = []
for i in range(len(d)-1):
  for j in range(i+1, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)

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

Submission status: Wrong Answer

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

    # divisors.sort()
    return divisors

N = int(input())

tmp = make_divisors(N)
print((tmp[-1]-1)+(tmp[-2]-1))

Submission status: Wrong Answer

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

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

    return 1

flag = is_prime(n)

if flag == 1:
    print(n-1)
else:
    if math.sqrt(n) == n/math.sqrt(n):
        print(int((math.sqrt(n)-1)*2))
    else:
        m = math.sqrt(n)*2
        s = int(m)-1
        print(s)

Submission status: Wrong Answer

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

factor = []

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

factor.append(N)

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

print(N2//A + A -2)

Submission status: Wrong Answer

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

a = int(math.sqrt(n))
for j in range(a,n):
	if n%j == 0 and n/j >0:
		print(int(n/j+j-2))
		break
	if j-a > 50:
		print(n-1)
		break

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque,defaultdict
from fractions import gcd
from math import ceil
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 N():
    return int(sys.stdin.readline())
def NK():
    return map(int,sys.stdin.readline().split())
def LS_I():
    return [int(x) for x in sys.stdin.readline().split()]
def LS_S():
    return list(input())
def main():
    n = N()
    a,b = 0,10**19
    for i in range(1,10**6):
        if n%i==0:
            if abs(n//i-i)<=abs(a-b):
                a,b = i,n//i

    print(a+b-2)

if __name__ == "__main__":
    main()

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]
a = 1
b = 1
for x in p:
    #print("a:{} b:{} x:{} p:{}".format(a, b, p[-1], p))
    if a < b:
        a = a * x
    else:
        b = b * x
#print("a:{} b:{}".format(a, b))
print(a - 1 + b - 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
#a,b = map(int,input().split())
#li = list(map(int,input().split()))

li = []

    
for i in range(2,int(n**0.5//1)):
    if n%i == 0:
        li.append(i+n//i-2)
if len(li)!=0:
    print(min(li))
else:
    print(n-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
bl = 0
i = 1
j = 1
a = 0
change_direction = 0
while bl == 0:
    if n == i * j:
        bl = 1
    if change_direction == 0:
        i = i + 1
        change_direction = 1
    else:
        j = j + 1
        change_direction = 0
    a = a + 1
print (a)

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(sum(divisors)-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
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

N = int(input())

prime_N = factorization(N)
prime_N = sorted(prime_N, reverse=True, key=lambda x: x[0])
A = 1
B = 1
for i in range(len(prime_N)):
    for j in range(prime_N[i][1]):
        if A*prime_N[i][0] < B*prime_N[i][0]:
            A *= prime_N[i][0]
        else:
            B *= prime_N[i][0]

print(A + B - 2)

Submission status: Wrong Answer

Solution code:
import math

def is_prime(num:int) -> bool:
    if num == 1: return False

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

    return True

def calc_prime(num: int) -> int:
    a = []
    while num % 2 == 0:
        a.append(2)
        num //= 2
    f = 3
    while f*f <= num:
        if num%f == 0:
            a.append(f)
            num //= f
        else:
            f += 2
    if num != 1:
        a.append(num)
    return a

n = int(input())

if is_prime(n):
    print(n-1)
else:
    p = calc_prime(n)
    ans = 10**12
    for _p in p:
        tmp = _p-1 + int(n/_p)-1
        if tmp <= ans:
            ans = tmp
    print(ans)

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

    print(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:
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    #table = list(set(table))
    table = list(table)
    table.sort()
    return table

N = int(input())

#for N in range(1000000000000):
n = []
n = divisor(N)
print(n)

cnt = 999999999999999
for i in range(0,len(n)//2,1):
    t = int(n[i])-1 + int(n[len(n)-i-1])-1
    if cnt > t:
        cnt = t
print(cnt)

Submission status: Wrong Answer

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

a = int(math.sqrt(n))
for j in range(a,n):
	if n%j == 0 and n/j >0:
		print(int(n/j+j-2))
		break
	if j > 50:
		print(n-1)
		break

Submission status: Wrong Answer

Solution code:

N=int(input())

com=[]
for i in range(N,2,-1):
    for j in range(1,i):
        if(i*j==N):
            tmp=[]
            tmp.append(i)
            tmp.append(j)
            com.append(tmp)
            break


min_s=pow(10,6)

for i in range(len(com)):
    s=com[i][0]-1+com[i][1]-1
    if(min_s>s):
        min_s=s

print(min_s)

Submission status: Wrong Answer

Solution code:
N = int(input())
res = float("inf")
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 = [1] + prime_factorize(N)
b = 1
c = 1
#print(a)
res = float("inf")
for i in range(len(a)):
  c *= a[i]
for i in range(len(a)):
  res = min(res, b + c)
  #print(res, b, c)
  b *= a[i]
  c //= a[i]
print(res - 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
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

N = int(input())

prime_N = factorization(N)
prime_N = sorted(prime_N, reverse=True, key=lambda x: x[0])
A = 1
B = 1
for i in range(len(prime_N)):
    for j in range(prime_N[i][1]):
        if A*prime_N[i][0] < B*prime_N[i][0]:
            A *= prime_N[i][0]
        else:
            B *= prime_N[i][0]
print(A, B)
print(A + B - 2)

Submission status: Wrong Answer

Solution code:
N = int(input())

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
 
if len(divisor(N)) < 3:
    print(N - 1)
else:
    divisor_list = divisor(N)
    tmp = N
    for i in divisor_list:
        print(i)
        A = i
        B = N / i
        if tmp > (A + B - 2):
            tmp = (A + B - 2)
    print(int(tmp))

Submission status: Wrong Answer

Solution code:
N = int(input())
num_a = 1
num_b = N
i = 2

while num_a <= num_b and i < N:
    print(i)
    if num_b % i == 0:
        num_a = num_a * i
        num_b = num_b / i    
    else:
        i += 1
print(num_a+num_b-2)

Submission status: Wrong Answer

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

n = int(input())

if is_prime(n) == True:
    print(n-1)
else:
    m = 0
    for i in range(round(n/2)):
        if n % (round(n/2)-i) == 0:
            ans = (round(n/2)-i)
            m += 1
            if m == 2:
                break
        
        
    ans2 = round(n/ans)
    print(ans+ans2-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.popleft()
b=1
c=0
for i in range(len(fac)-1):
	if a <= b:
		if c % 2 != 0:
			a *= dfac.popleft()
		else:
			a *= dfac.pop()
	else:
		if c % 2 != 0:
			b *= dfac.popleft()
		else:
			b *= dfac.pop()
	c+=1
print("%d" % (a+b-2))

Submission status: Wrong Answer

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

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 i == len(yakusu_list)-1:
        if yakusu == 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
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:
n = int(input())


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

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

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

    return arr


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

# max_y = fact[-1][0]
# 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:
# 入力
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

num_parts = prime_factorize(N)
n1 = 1
n2 = 1
for num in num_parts[::-1]:
    if n1 <= n2:
        n1 = n1 * num
    else:
        n2 = n2 * num
print(n1-1+n2-1)

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import itertools

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

N = int(input())
listN = factorize(N)
x = 0
y = 0

mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(1,len(listN)):
        tmp = list(itertools.combinations(listN,i))
        for j in range(len(tmp)):
            x0,y0 = 1,1
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                y0 = N//x0
                print(x0,y0)
                if mini > abs(x0+y0):
                    mini = abs(x0+y0)
                    x = x0
                    y = y0

print(x-1+y-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
n1=n
ans=n
for i in range(1,n):
    if n1%i==0:
        n1=n1//i
        ans=min(ans,i+n//i-2)
    if n1/i<=1:break

print(ans)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())

ns = [int(i) for i in str(n)]
a = 0
b = 0
ans = 0
f = 0

# def search():
#     for i in range(int(math.sqrt(n)),0,-1):
#         print(i)
#         if n % i == 0:
#             a = i
#             b = n // i
#             break
#     else:
#         ans = n - 1

if ns[-1] % 2 == 0 or sum(ns) % 3 == 0 or ns[-1] == 5:
    y = math.sqrt(n)
    for i in range(int(y),1,-1):
        if n % i == 0:
            a = i
            b = n // i
            break
    else:
        ans = n - 1
        f = 1
else:
    z = math.sqrt(n)
    for i in range(7,int(z)+1,2):
        if n % i == 0:
            a = i
            b = n // i
            break
        else:
            ans = n - 1
            f = 1

# print('a',a)
# print('b',b)

if f:
    print(ans)
else:
    ans = a - 1 + b - 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import fractions
import random
import functools

N = int(raw_input())

def lcg(n, c, x):
    '''
    a pseudorandom number generator (known as Linear Congruential Generator)
    '''
    return (x * x + c) % n


class memoize(object):
    '''
    a decorator function class to memoize a expensive function.
    '''
    def __init__(self, func):
        self._func = func
        self._cache = {}

    def __call__(self, *args):
        if self._cache.has_key(args):
            return self._cache[args]
        res = self._func(*args)
        self._cache[args] = res
        return res


@memoize
def is_prime(n, accuracy=20):
    '''
    check if `n` is probable prime using Rabin Miller method.
    to get more reliability, increase `accuracy` parameter.
    '''
    n = abs(n)
    if n == 2:
        return True
    if n == 1 or not n & 1:
        return False
    d = n - 1
    while not d & 1:
        d >>= 1
    for i in range(accuracy):
        a = random.randrange(n - 2) + 1
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1
        if y != n - 1 and not t & 1:
            return False
    return True


def trial_division(n):
    '''
    find the smallest divisor of the integer `n` with Trial Division method.
    returns -1 if it is a prime.
    '''
    limit = int(math.sqrt(n) + 1)
    for i in range(2, limit):
        if not n % i:
            return i
    return -1


def pollards_rho(n, c=1):
    '''
    find the one of divisors of the composite number `n` with Pollard's Rho method.
    returns -1 if it is a prime.
    to get another result, change `c` parameter.
    warning: less reliable for small composite numbers.
    '''
    x, y, d = 2, 2, 1
    f = functools.partial(lcg, n, c)
    while d == 1 and n:
        x = f(x)
        y = f(f(y))
        d = fractions.gcd(x - y, n)
        if d == n:
            return -1
    return d


@memoize
def factor(n, accuracy=10):
    '''
    factorize the integer `n`.
    returns list of prime factors.
    '''
    if is_prime(n):
        return [n]
    if n < 100:
        # fallbacks to trial division for a small integer
        divisor = trial_division(n)
    else:
        # `accuracy` is diverted to the constant of Pollard's Rho
        divisor = pollards_rho(n, accuracy)
    if divisor == -1:
        if accuracy:
            # repeat with another constant
            return factor(n, accuracy - 1)
        return [n]
    return factor(n / divisor) + factor(divisor)

def compose(xs):
    if len(xs) <= 1:
        return xs + [1]
    if len(xs) == 2:
        return xs
    xs.sort()
    return compose([xs[0] * xs[1]] + xs[2:])

factors = list(reversed(factor(N)))
i, j = compose(factors)
print (i - 1) + (j - 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N=int(input())

def factorization(n):
    arr = [1]
    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=temp//i
            if cnt==1:
                arr.append(i)
            else:
                arr=arr+[i]*cnt
    if temp!=1:
        arr.append(temp)

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

    return arr

ans=factorization(N)

import heapq

while len(ans)>2:
    temp1=heapq.heappop(ans)
    temp2=heapq.heappop(ans)
    heapq.heappush(ans,temp1*temp2)

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

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)

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())
 
k = math.floor(math.sqrt(N))
  
for i in range(1,k)[::-1]:
  if N%i==0:
      print(int(N/i)+i-2)
      exit()

Submission status: Wrong Answer

Solution code:
import math

def is_prime(num:int) -> bool:
    if num == 1: return False

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

    return True

def calc_prime(num: int) -> int:
    a = []
    while num % 2 == 0:
        a.append(2)
        num //= 2
    f = 3
    while f*f <= num:
        if num%f == 0:
            a.append(f)
            num //= f
        else:
            f += 2
    if num != 1:
        a.append(num)
    return a

n = int(input())

if is_prime(n):
    print(n-1)
else:
    p = calc_prime(n)
    ans = 10**12
    for _p in p:
        tmp = _p-1 + int(n/_p)-1
        if tmp <= ans:
            ans = tmp
    print(tmp)

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:
      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:
# coding: utf-8
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)
# print(a)
m=len(a)
# print(m)

if(m == 1):
    b=a[0]
    c=1
elif(m == 2):
    b=a[0]
    c=a[1]
elif(m == 3):
    b=a[0]*a[2]
    c=a[1]
else:
    for i in range(int(m/2)):
        b=a[i]*a[m-1-i]
        c=a[i+1]*a[m-2-i]
    if m % 2 != 0:
        c=c*a[int(m/2) + 1]

print (b+c-2)

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
m = (len(L)+1)//2+1+1
for i in range(1,m):
    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)