Problem:


Score : 300 points

Problem Statement

Takahashi is standing on a multiplication table with infinitely many rows and columns.

The square (i,j) contains the integer i \times j. Initially, Takahashi is standing at (1,1).

In one move, he can move from (i,j) to either (i+1,j) or (i,j+1).

Given an integer N, find the minimum number of moves needed to reach a square that contains N.

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the minimum number of moves needed to reach a square that contains the integer N.

Sample Input 1

10

Sample Output 1

5

(2,5) can be reached in five moves. We cannot reach a square that contains 10 in less than five moves.

Sample Input 2

50

Sample Output 2

13

(5, 10) can be reached in 13 moves.

Sample Input 3

10000000019

Sample Output 3

10000000018

Both input and output may be enormous.



Sample input:
10


Sample output:
5

Submission status: Wrong Answer

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

N = int(input())
n = max(prime_factorize(N))

print(int(N/n + n - 2))

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def main(N):
    min_dis = None
    for i in range(1, 10):
        if N % i == 0 and N % i <= 9:
            j = int(N / i)
            n_dis = i + j - 2
            if min_dis is None or n_dis < min_dis:
                min_dis = n_dis
    return min_dis


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

Submission status: Wrong Answer

Solution code:
n = int(input())
count = True
tmp = 1
output = n - 1

while count:
    for i in range(2, 8):
        if n % i == 0:
            tmp *= i
            n //= i
            if (n - 1) + (tmp - 1) < output:
                output = (n - 1) + (tmp - 1)
            break

        count = False

print(output)

Submission status: Wrong Answer

Solution code:
import collections
import heapq as hq
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 = collections.Counter(prime_factorize(N))
B = []
hq.heapify(B)
for i,j in A.items():
    while j != 0:
        hq.heappush(B,i)
        j -= 1
leng = len(B)
if leng == 1:
    print(B[0]-1)
    exit()

while leng > 2:
    a = hq.heappop(B)
    b = hq.heappop(B)
    hq.heappush(B,a*b)
    leng -= 1
print(sum(B)-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])


    arr.append([n, 1])

    return arr
  
N = int(input())
A = factorization(N)
print(A)
ans =[]
for a in A:
  for i in range(a[1]):
    ans.append(N//a[0]+a[0]-2)

print(int(min(ans)))

Submission status: Wrong Answer

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

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):
        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:
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):
    if 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
    for i, next_ in enumerate(a):
        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 = int(math.sqrt(N))

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

Submission status: Wrong Answer

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

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

def 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()
    lis = make_divisors(n)
    #print(lis)
    p = (len(lis)-1) // 2
    print(lis[p] + lis[p+1] - 2)

if  __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())


def solve(n):
    if n == 1:
        return 0
    for i in range(2, n):
        # print(">>> step:", i)
        c = i - i // 2
        # print(c)
        for j in range(c):
            # print(i - j, j + 1)
            if (i - j) * (j + 1) == n:
                return i - 1


print(solve(n))

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

div_list = prime_factorize(N)
ans = N - 1 
for i in div_list:
    tmp = i - 1 + (N // i - 1)
    ans = min(tmp, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

left_side = 1
right_side = N

# 平方根から下げていく
square = int(math.sqrt(N))
for i in reversed(range(1, square)):
    if N % i == 0:
        left_side = i
        right_side = N // i
        break

distance = (left_side - 1) + (right_side - 1)
print(distance)

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((n//i, i))
            if i != n // i:
                divisors.append((n//i, i))
    return set(divisors)


pairs = list(make_divisors(n))
min_pair = n-1
for p in pairs[1:]:
    result = p[0] + p[1] -2
    if result < min_pair:
        min_pair = result

print(min_pair)

Submission status: Wrong Answer

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

max = math.floor(N**0.5)
A = 1
B = 1

for i in range(max):
    if N % (max - i) == 0:
        A = (max - i)
        B = N // A

print(A + B - 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
ans=1000000000000

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

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

num = max(factorize(n))
ans = int(num -1 + (n / num) -1)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
x = n
for i in range(n):
    for j in range(n):
        if (i+1)*(j+1) == n:
            if i+1 + j+1 < x:
                x = i+1 + j+1
print(x-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = 1
while a**2>n:
  a += 100
ans = n
for i in range(a):
  if n % (i+1) == 0:
    b = n/(i+1) + (i+1) -2
    if b < ans:
      ans = b
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 = int(input())
A = factorization(N)
ans =[]
for a in A:
  for i in range(a[1]):
    ans.append(N//a[0]+a[0]-2)

print(int(min(ans)))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

from collections import deque

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_tmp = deque(prime_factorize(N))
N_tmp, N_tmp1, N_tmp2= 0, 1, 1
A_len = len(A_tmp)
counter = 1

while True:
    if A_tmp == deque([]):
        break
    else:
        N_tmp = A_tmp.popleft()
        if N_tmp1 >= N_tmp2:
            N_tmp2 = N_tmp * N_tmp2
        else:
            N_tmp1 = N_tmp * N_tmp1
print(N_tmp1 + N_tmp2 - 2)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
sn=int(math.sqrt(n))
tl=list(range(1,sn+1))
ans=0
for i in range(1,sn+1):
    a=n/tl[-i]
    if a.is_integer():
        ans=int(a)
        break
b=int(n/ans)
print(n,ans,b)
print(ans-1+b-1)

Submission status: Wrong Answer

Solution code:
import math
#試し割法
def factorization(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return [n]
    else:
        factor.append(n)
        return factor


n = int(input())

a = 1
b = 1

fct = factorization(n)

for x in reversed(fct):
    if a <= b:
        a *= x
    else:
        b *= x

print(a+ b - 2)

Submission status: Wrong Answer

Solution code:
import collections


def num_check(N):
    for i in reversed(range(2, 100)):
        q, mod = divmod(N, i)
        if mod == 0:
            return i, q

    return 1, N


def num_check1(num):
    ans = []
    for i in range(1, num):
        if num % i == 0:
            ans.append(i)
    return ans


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


if __name__ == "__main__":
    N = int(input())
    c = collections.Counter(prime_factorize(N))
    num = c.most_common()[0][0]
    ans = int(num + (N / num))
    print(ans - 2)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
sq = pow(n, 0.5)
flg = False
for i in (2, sq):
    if n % i == 0:
        flg = True
if flg:
    print(math.floor(sq) * 2 - 1)
else:
    print(n - 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
ans = n
tmp = 0

for i in range(n):
    for j in range(n):
        if i * j == n:
            l.append([i,j])

for i in l:
    tmp = i[0] + i[1] -2
    if ans > tmp:
        ans = tmp

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

lst = prime_factorize(N)
#print(lst)
if len(lst) == 1:
    print(N - 1)
else:
    '''
    if len(lst) % 2 == 0:
        for i in range(len(lst) // 2):
            a *= lst[i]
        for j in range(len(lst) // 2 , len(lst)):
            b *= lst[j]
        print(a + b - 2)
    else:
        for i in range(len(lst) // 2 + 1):
            a *= lst[i]
        for j in range(len(lst) // 2 + 1, len(lst)):
            b *= lst[j]
        print(a + b - 2)
    '''
    min_val = float('inf')
    for i in range(len(lst)):
        a = 1
        b = 1
        work_lst1 = lst[:i + 1]
        work_lst2 = lst[i + 1:]
        for i in range(len(work_lst1)):
            a *= work_lst1[i]
        for j in range(len(work_lst2)):
            b *= work_lst2[j]
        tmp_min = a + b - 2
        if min_val > tmp_min:
            min_val = tmp_min
    print(min_val)

Submission status: Wrong Answer

Solution code:
import math
s=input()
b=0
c=0
a=int(s)
d=int(math.sqrt(a))
for i in range(1,d,1):
  if a%i==0:
    b=i
    c=a/i
e=int(b-1+c-1)
print(e)

Submission status: Wrong Answer

Solution code:
N = int(input())


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


def solve(N):
    list_N = prime_decomposition(N)
    ans = N - 1
    for i in list_N:
        ans_tmp = ((N / i) - 1) + (i - 1)
        if ans > ans_tmp:
            ans = ans_tmp

    return ans


print(solve(N))

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




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if __name__ == "__main__":
    a = int(input())
    a = int(a)
    b = prime(a)
    c = len(b)
    while len(b) > 2:
        b.sort()
        b1 = b.pop(0)
        b2 = b.pop(0)
        b3 = b1 * b2
        b.insert(0, b3)
    print(sum(b)-len(b))

Submission status: Wrong Answer

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

lst = prime_factorize(N)
print(lst)
if len(lst) == 1:
    print(N - 1)
else:
    '''
    if len(lst) % 2 == 0:
        for i in range(len(lst) // 2):
            a *= lst[i]
        for j in range(len(lst) // 2 , len(lst)):
            b *= lst[j]
        print(a + b - 2)
    else:
        for i in range(len(lst) // 2 + 1):
            a *= lst[i]
        for j in range(len(lst) // 2 + 1, len(lst)):
            b *= lst[j]
        print(a + b - 2)
    '''
    min_val = float('inf')
    for i in range(len(lst)):
        a = 1
        b = 1
        work_lst1 = lst[:i + 1]
        work_lst2 = lst[i + 1:]
        for i in range(len(work_lst1)):
            a *= work_lst1[i]
        for j in range(len(work_lst2)):
            b *= work_lst2[j]
        tmp_min = a + b - 2
        if min_val > tmp_min:
            min_val = tmp_min
    print(min_val)

Submission status: Wrong Answer

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

max = math.floor(N**0.5)
A = 1
B = 1

for i in range(max):
    if N % (max - i) == 0:
        A = N
        B = N // A

print(A + B - 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())

arr = factorization(N)


A = []
for a in arr:
    for i in range(a[1]):
        A.append(a[0])

ans = 1
for i in A[:len(A)-1]:
    ans *= i

ans += A[len(A)-1]-2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
import math 
arr = []
num = math.ceil(n**0.5)
for i in range(1,num):
  if n % i == 0:
    arr.append(i+n/i-2)
print(int(min(arr)))

Submission status: Wrong Answer

Solution code:
i = 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 = []
for x, y in zip(make_divisors(i), reversed(make_divisors(i))):
	l.append(x + y - 2)
print(min(l))

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())
F = [1]
for i, j in factorization(n):
    for _ in range(j):
        F.append(i)
R = []
tmp = F[0]
R.append(tmp)
for i in range(1, len(F)):
    tmp *= F[i]
    R.append(tmp)
L = []
tmp = F[-1]
L.append(tmp)
for i in reversed(range(len(F) - 1)):
    tmp *= F[i]
    L.append(tmp)
L = list(reversed(L))
ans = 9999999999999
for i in range(len(R) - 1):
    r = R[i]
    l = L[i+1]
    tmp = (r-1) + (l-1)
    if tmp < ans:
        ans = tmp
print(tmp)

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)
            
print(divisors[-1]+divisors[-2]-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):
        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]
print(yakusu_pair_list)
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:
def sol(n):
    ans = float('inf')
    x1 = 1
    while n % 2 == 0:
        x1 *= 2
        n //= 2
        ans = min(x1+N//x1-2,ans)
    f = 3
    while f * f <= n:
        if n % f == 0:
            x1 *= f
            n //= f
            ans = min(x1+N//x1-2,ans)
        else:
            f += 2
    return min(x1+N//x1-2,ans)

N = int(input())
print(sol(N))

Submission status: Wrong Answer

Solution code:
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()
a=1
b=1
c = 0
for i in range(len(fac)//2):
	if c % 2 == 0:
		a *= fac[2*i]
		b *= fac[2*i+1]
	else:
		a *= fac[2*i+1]
		b *= fac[2*i]
	c+=1
if len(fac)%2 == 1:
	a *= fac[c]
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

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

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = 0
b = 0
ans = 0
for i in range(int(math.sqrt(n)),1,-1):
  print(i)
  a = i
  b = n/i
  if b%1 == 0 and b<10:
    ans = a+b-2
    break
print(ans)

Submission status: Wrong Answer

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


if __name__ == "__main__":
    N = int(input())

    div = factorize(N)
    div.reverse()

    A, B = 1, 1

    ans = 0
    for i in div:
        ans += i

    if len(div) == 1:
        ans += 1

    print(ans-2)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    x = int(input())
    ans = 1500000000
    for i in range(x, 0, -1):
        if x % i == 0:
            q = (int(x/i) - 1) + (i-1)
            if q < ans:
                ans = q
            else:
                print((int(x/i) - 1) + (i-1))
                break

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

    length = len(primes)
    point = length // 2 if length % 2 == 0 else length // 2 + 1
    print(reduce(mul, primes[0:point]) + reduce(mul, primes[point:]) - 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:
# coding: utf-8


def main(N):
    min = None
    for i in range(1, 10):
        j = int(N / i)
        # print('loop', i)
        if N % i == 0 and j <= 9:
            n_distance = i + j - 2
            if min is None or n_distance < min:
                min = n_distance
    return min


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

Submission status: Wrong Answer

Solution code:
n = int(input())
x = n
for i in range(n):
    for j in range(n):
        if (i+1)*(j+1) == n:
            if i+1 + j+1 < x:
                x = i+1 + j+1
print(x)

Submission status: Wrong Answer

Solution code:
N = int(input())

for i in range(1,N+1,1):
    if i % N == 0:
        print(i+(N//i)-2)
        break

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

    # divisors.sort()
    return divisors
N=int(input())
S=[]
l=0
m=0
n=0
a=len(make_divisors(N))
for i in make_divisors(N):
  S.append(i)
S.sort()
l=len(S)
m=S[l//2-1]
n=N//m
print((m-1)+(n-1))

Submission status: Wrong Answer

Solution code:
n = int(input())
r = int(n**0.5)
while r>0:
    if n % r == 0:
        print(int(r + n/r - 2))
        break
    else:
        r =- 1

Submission status: Wrong Answer

Solution code:
N = int(input())


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

    divisors.sort()
    return divisors


divs = make_divisors(N)
i = len(divs) // 2 - 1
print(divs[i]-1 + N // divs[i]-1)

Submission status: Wrong Answer

Solution code:
import math
from fractions import gcd

def trial_division(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    if not factor:
        return [1, n]
    else:
        factor.append(n)
        return factor

n1 = int(input())
n2 = trial_division(n1)

c1 = 1
c2 = 1
n2.sort()

for i1 in range(len(n2)):
    if c1 < c2:
        c1 = c1 * n2[i1]
    else:
        c2 = c2 * n2[i1]

r1 = c1 + c2 - 2
print(r1)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

facro = factorization(N)
print(facro[0] +facro[1] -2)

Submission status: Wrong Answer

Solution code:
n = int(input())
min = n+1
kaisu = int((n/4)-1)

for i in range(kaisu):
    if n%(i+1)==0:
        tmp = i+(n/(i+1))-1
        if min > tmp:
            min = tmp
    if (i+1)**2>n:
        break

print(int(min))

Submission status: Wrong Answer

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

    #divisors.sort()
    return divisors

N=int(input())
L=make_divisors(N)
print(L[len(L)-1]+L[len(L)-2]-2)

Submission status: Wrong Answer

Solution code:
n=int(input())
fac=1
if n%2==0:
  fac=2
if n%3==0:
  fac=3
s=n**(1/2)//6+1
for i in range(1,int(s)):
  if n%(i*6-1)==0:
    fac=i*6-1
  if n%(i*6+1)==0:
    fac=i*6+1
fac+=n//fac-2
print(fac)

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)
    while len(x) > 2:
        a = heapq.heappop(x)
        b = heapq.heappop(x)
        heapq.heappush(x, a*b)
    c = heapq.heappop(x)
    d = heapq.heappop(x)
    print(c+d-2)

Submission status: Wrong Answer

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

if __name__ == "__main__":
    a = int(input())
    a = int(a)
    b = prime(a)
    c = len(b)
    while len(b) > 2:
        b1 = b.pop(0)
        b2 = b.pop(0)
        b3 = b1 * b2
        if b[0] >= b3:
            b.insert(0, b3)
        else :
            b.insert(-1, b3)
    print(sum(b)-len(b))

Submission status: Wrong Answer

Solution code:
N=int(input())
import math
SQ=int(math.sqrt(N))
minval=10**12
a=1
b=1
for i in range(1,SQ):
  if N%i==0:
    newa=i
    newb=N//i
    if abs(newa-newb) < minval:
      minval=abs(newa-newb)
      a=newa
      b=newb

print(a+b-2)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=n**0.5
d=[]
for i in range(1,int(n**0.5)+1):
  if n%i==0:
    d.append(i)
    if i!=n//i:
      d.append(n//i)
d.sort()
import bisect as bi
b=bi.bisect_left(d,s)
print(n//d[b-1]+d[b-1]-2)

Submission status: Wrong Answer

Solution code:
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()
a=1
b=1
c = 0
for i in range(len(fac)//2):
	if c % 2 == 0:
		a *= fac[2*i]
		b *= fac[2*i+1]
	else:
		a *= fac[2*i+1]
		b *= fac[2*i]
	c+=1
print("%d %d" % (a,b))
if len(fac)%2 == 1:
	a *= fac[c]
print("%d" % (a+b-2))