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

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

Submission status: Runtime Error

Solution code:
n = int(input())
ans = n
for i in range(0,int(n**0.5)):
  if n % i == 0:
    j = target // i
    if (i+j-2) < ans:
      ans = i+j-2
print(ans)

Submission status: Runtime Error

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

for i in range(1,target**0.5):
  if target % i == 0:
    j = target // i
    if (i+j-2) < curAns:
      curAns = i+j-2
print(curAns)

Submission status: Runtime Error

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

for i in range(1,target**0.5):
  if target % i == 0:
    j = target // i
    if (i+j-2) < curAns:
      curAns = i+j-2
print(curAns)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
=int(input())
count=1
ans=10000000000000
k=c
for i in range(1,int(c**(1/2)+100000)):
    if c%i==0:
        count*=i
        k=int(k/i)
        if ans>count+k:
            ans=count+k
            count=0
            k=c
        else:
            count=0
            k=c
print(ans-2)

Submission status: Runtime Error

Solution code:
c=int(input())
count=1
ans=10000000000000
k=c
a=[]
for i in range(1,int(c**(1/2))):
    if c%i==0:
        count*=i
        k=int(k/i)
        a.append(count+k)
        count=1
        k=c
print(a)
print(min(a)-2)

Submission status: Runtime Error

Solution code:
c=int(input())
count=1
ans=10000000000000
k=c
a=[]
for i in range(1,int(c**(1/2))):
    if c%i==0:
        count*=i
        k=int(k/i)
        a.append(count+k)
        count=1
        k=c
print(a)
print(min(a)-2)

Submission status: Runtime Error

Solution code:
c=int(input())
count=1
ans=10000000000000
k=c
a=[]
for i in range(1,int(c**(1/2))):
    if c%i==0:
        count*=i
        k=int(k/i)
        a.append(count+k)
print(min(a)-2)

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue
from heapq import heappop, heappush
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
res = float('inf')
for i in range(1,math.sqrt(n)):
    if n%i == 0:
        res = min(res, i + n/i)
print(int(res-2))

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
root=int(np.sqrt(N))+1
a=1
b=N
for i in range(root, 0, -1):
    if N%i==0:
        a=i
        b=N//i
        break
print(a-1+b-1)

Submission status: Runtime Error

Solution code:
# coding: utf-8

n = int(input())
a = b = 1


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
    
    
list_bunkai = prime_factorize(n)     #上記の関数による，試し割り法での素因数分解

if len(list_bunkai) > 2:             #要素数が2より大きい場合
    while a <= min(list_bunkai):
        a *= min(list_bunkai)
        list_bunkai.remove(min(list_bunkai))
else:                                #要素数が2の場合（nが1でしか割れない場合）
    a = min(list_bunkai)
    list_bunkai.remove(min(list_bunkai))
    

if len(list_bunkai) != 0:            #要素が1以上残っているなら，他の値を掛け合わせる
    for i in list_bunkai:
        b *= i 
    

print(a +b -2)                       #出力

Submission status: Runtime Error

Solution code:
N = int(input())

import math

A = int(math.sqrt(N))

for i in reversed(range(A)):
    if N % i == 0:
        print(i + (N // i) - 2)
        exit()

Submission status: Runtime Error

Solution code:
import math
import sys

n = int(input())

low = sys.maxsize
a, b = 0, 0
for i in range(math.floor(math.sqrt(n))):
    if n%i == 0 and (i + n//i) <= low:
        a, b = i, n//i
        low = a + b
print(a+b-2)

Submission status: Runtime Error

Solution code:
i = int(input())
list = []

if i % 2 == 0:
    for m in range(2, int((i+2)/2) + 1):
        if i % m == 0:
            list.append(m + i / m)

if i % 2 == 1:
    for m in range(1, int((i+1)/2), 2):
        if i % m == 0:
            list.append(m + i / m)


list.sort()
print(int(list[0]-2))

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())

patterns = []

for i in range(1, int(np.sqrt(n))):
	if n % i == 0:
		patterns.append(i + n // i - 2)

print(min(patterns))

Submission status: Runtime Error

Solution code:
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))
        tmp = list(set(tmp))
        for j in range(len(tmp)):
            x0,y0 = 1,1
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                y0 = N//x0
                if mini > abs(x0+y0):
                    mini = abs(x0+y0)
                    x = x0
                    y = y0
print(x-1+y-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
from functools import reduce
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
A = factorize(N)
for i in range(1,len(A)):
    x = 1
    y = 1
    for a in A[0:i]:
        x *= a
    for a in A[i:]:
        y *= a
ans = x+y-2

ans = N-1 if len(A) == 1else ans
print(ans)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
for i in range(int(math.sqrt(N)), 0, -1):
  if N / i == int(N / i):
      print(int(N / i + i - 2))
      sys.exit()

Submission status: Runtime Error

Solution code:
N = int(input())
for i in range(1, N**0.5):
  if N%i == 0:
    print(i+N//i-2)

Submission status: Runtime Error

Solution code:
N = int(input())

count = 0
odd = []
even = []
idou = []

for a in range(2, N):
    if N % a == 0:
        if count == 0:
            odd.append(a)
            count = 1
            if N / (a * a) == 1:
                even.append(a)
                count = 0

        elif count == 1:
            even.append(a)
            count = 0
            if N / (a * a) == 1:
                odd.append(a)
                count = 1

for c in range(len(odd)):
    idou.append(odd[c] + even[len(odd)-c-1])

result = min(idou) - 2

print(result)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
m=N+1
for j in range(2,math.sqrt(N)):
    if N%j==0:
        a=j
        b=N//j
        if a>b:
            break
        else:
            m=min(m,(a+b))

print(m-2)

Submission status: Runtime Error

Solution code:
N = int(input())
for i in range(N**0.5):
  if N%i == 0:
    print(i+N//i-2)

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import pdb
import sys
import math
F = sys.stdin
a, b, x = F.readline().rstrip().split()
a = int(a)
b = int(b)
x = int(x)
h = x / (a**2)
h2 = x/a
y = a * b / 2


if h2 <= y:
    c = 2*h2/b
    ans = math.degrees(math.atan(c/b))
    print(90 - ans)

if h2 > y:
    c = (2*h2/a) - b
    ans = math.degrees(math.atan(a/(b-c)))
    print(90 - ans)

Submission status: Runtime Error

Solution code:
for line in sys.stdin:
    A, B = list(map(int, line.split(' ')))

Submission status: Runtime Error

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:
             abc.append(n//i)
             continue
a = input()
a = int(a)
divisor(a)
#print(ab)
#print(abc)
print(ab[-1]+abc[-1]-2)

Submission status: Runtime Error

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:
             abc.append(n//i)
             continue
a = input()
a = int(a)
divisor(a)
print(ab)
print(abc)
print(ab[-1]+abc[-1]-2)

Submission status: Runtime Error

Solution code:
import numpy as np

m = np.array(int(input()))

a = 1
b = m

# for i in reversed(range(2, int(round(np.sqrt(n))))):
#     if n % i ==  0:
#         a = int(i)
#         b = int(n / i)
#         break

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

soin = prime_factorize(n)

soin_r = soin[::-1]

tmp = 1
for i in range(len(soin) // 2):
    tmp *= soin[i]

zan = m / tmp

print(int(tmp + zan - 2))

"""
10
5

50
13

10000000019
10000000018

"""

Submission status: Runtime Error

Solution code:
import math
import itertools

N = int(input())

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

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

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

    return arr

factrist = factorization(N)

tmplist = []

a = 1
b = 1

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

sq_N = math.sqrt(N)

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

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

        ans_list = []

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



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

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


        hoge = N / b / a / ans_list[boader-1]; 
        print(a * ans_list[boader-1] + b * hoge - 2)
        return

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = 0
b = 0

for i in range(1, n+1):
    if n%i = 0:
        if a == n/i:
            b = i
        else:
            a = i

print(a+b-2)

Submission status: Runtime Error

Solution code:
def division(n):
  factors = []
  tmp = int(n**0.5) + 1
  for num in range(2,tmp):
    while n % num == 0:
      n = n // num
      factors.append(num)
  if not factors:
    return [1, n]
  else:
    factors.append(n)
    return factors

def multiple(arr):
  new_arr = []
  mul = arr[0] * arr[1]
  del arr[0:2]
  arr.append(mul)
  arr.sort()
  return arr


input = int(input())
factors = division(input)
while len(factors) != 2:
  factors = multiple(factors)
answer = factors[0] + factors[1] - 2
print answer

Submission status: Runtime Error

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:
            abc.append(n//i)
            continue
a = input()
a = int(a)
if math.sqrt():

divisor(a)
print(ab)
print(abc)
print(ab[-1]+abc[-1]-2)

Submission status: Runtime Error

Solution code:
n = int(input())
num = 0
for i in range(1, n // 2):
    if n % i == 0:
        num = i
num2 = n / num
print(num + num2 - 2)

Submission status: Runtime Error

Solution code:
import copy
N = input()

keep = copy.copy(N)

yaksuu = []

a = 2

while N >= a:
    if N%a == 0:
        N /= a
        yaksuu.append(a)
    else:
        a += 1


yaksuu.append(N)

now = 1

ans = 100000000000000

for i in range(0,len(yaksuu)):
    now *= yaksuu[i]
    keep /= yaksuu[i]
    if now + keep -2 <= ans: ans = ans = now + keep -2

print(ans)

Submission status: Runtime Error

Solution code:
"""
https://atcoder.jp/contests/abc144/tasks/abc144_c
"""
from itertools import product, repeat
import numpy as np


def calc_too_late(N: int) -> int:
    for i in range(int(np.floor(np.sqrt(N))), N):
        # i*j で表せないのでスキップ
        if N % i != 0:
            continue

        j = N // i
        return i + j - 2

    return N - 1


def calc(N: int) -> int:
    nearest = N - 1
    factors = prime_factorization(N)
    for mask in product(*repeat([True, False], len(factors))):
        factor_a = np.prod(factors[mask])
        if N % factor_a != 0:
            continue
        factor_b = N // factor_a
        nearest = min(nearest, factor_a + factor_b - 2)

    return nearest


def prime_factorization(m: int) -> np.ndarray:
    """
    https://qiita.com/chun1182/items/ddf2b6cba932b2bb0d4e
    """
    # pf = {}
    pf = []
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            # pf[i] = pf.get(i, 0) + 1
            pf.append(i)
            m //= i
    if m > 1:
        # pf[m] = 1
        pf.append(m)
    # return pf
    return np.array(pf)


def load_input_as_int_array() -> np.ndarray:
    return np.array([int(v) for v in input().split(" ")])


def main() -> None:
    N, = load_input_as_int_array()
    result = calc(N)
    print(result)


main()

Submission status: Runtime Error

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

horizontal -= 1
print(horizontal + int(N / horizontal) - 1)

Submission status: Runtime Error

Solution code:
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list
ya=make_divisor_list(N)
answer=[]
 
lenarray=len(ya)
if lenarray%2==0:
  for i in range(lenarray//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)
else:
  for i in range((lenarray-1)//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)
 
 
  y=ya[0]
  answer.append(y*2)
  
print(min(answer)-2)
N=int(input())

ya = []

for i in range(1,N+1):
    if N % i == 0:
        ya.append(i)
answer=[]

lenarray=len(ya)
if lenarray%2==0:
  for i in range(lenarray//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)
else:
  for i in range((lenarray-1)//2):
    x=ya.pop(0)+ya.pop(-1)
    answer.append(x)


  y=ya[0]
  answer.append(y*2)
  
print(min(answer)-2)

Submission status: Runtime Error

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

Submission status: Runtime Error

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
 
a=make_divisors(N)
c=[]
for i in a:

    if (i-1)*((N/i)-1)>0:
        c.append((i-1)+((N/i)-1))

print(min(c))

Submission status: Runtime Error

Solution code:
import math

N = input()
rt = int(math.sqrt(N))
 
a = rt
while a>0:
    x = N/a
    if x.is_integer():
        x = int(x)
        break
    a = a-1
    
if a == 0:
    print(N-1)
else:
    print(a+x-2)

Submission status: Runtime Error

Solution code:
N = int(input())
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

a = make_divisors(N)
if len(a)%2 == 1:
  print(2*int(math.sqrt(N))-2)
if len(a)%2 == 0:
  b = a[int(len(a))/2-1]
  c = a[int(len(a))/2]
  print(b+c-2)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
l =[]
for i in range(1,1000000):
  if type(N/i) == int:
    l.append(i + N/i)
print(min(l)-2)

Submission status: Runtime Error

Solution code:

from functools import reduce
from operator import mul
from collections import Counter

def prod(arr):
    return reduce(mul, arr, 1)

def fancy(arr, index):
    output = []
    for i, v in enumerate(index):
        if v:
            output.append(arr[i])
    return output

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

N = int(input())
factors = prime_factorize(N)
counter = Counter(factors)
odd_factors = [factor for factor in factors if counter[factor]%2!=0]
even_factors = [factor for factor in factors if counter[factor]%2==0]

if odd_factors:
    N_odd = prod(odd_factors)
    selectors = [list(map(bool, map(int, list("{0:b}".format(i).zfill(len(odd_factors)))))) for i in range(1, 2**len(odd_factors))]
    even_coeff = prod(even_factors[::2]) if even_coeff else 1
    combinations = [(prod(fancy(factors, selector))*even_coeff, even_coeff*N_odd//prod(fancy(factors, selector))) for selector in selectors]
    
else:
    combinations = [(int(N**0.5), int(N**0.5))]
distances = [combination[0]-1 + combination[1]-1 for combination in combinations]
print(min(distances))

Submission status: Runtime Error

Solution code:
import math
N = int(input())
ans = N-1
n = math.sqrt(N)
n = int(n)+1
for i in range(1, n)
    if N%i==0:
        tmp = N//i
        ans = (tmp-1)+(i-1)

    
print(ans)

Submission status: Runtime Error

Solution code:
def division(n):
  factors = []
  tmp = int(n**0.5) + 1
  for num in range(2,tmp):
    while n % num == 0:
      n //= num
      factors.append(num)
  if not factors:
    return [1, n]
  else:
    factors.append(n)
    return factors

def multiple(arr):
  new_arr = []
  mul = arr[0] * arr[1]
  del arr[0:2]
  arr.append(mul)
  arr.sort()
  return arr


input = int(input())
factors = division(input)
while len(factors) != 2:
  factors = multiple(factors)
answer = factors[0] + factors[1] - 2
print answer

Submission status: Runtime Error

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(1)
    else:
        pass
    break
if 
f=sum(factor)-2
print(f)

Submission status: Runtime Error

Solution code:
N = input()
rt = int(math.sqrt(N))
 
a = rt
while a>0:
    x = N/a
    if x.is_integer():
        x = int(x)
        break
    a = a-1
    
if a == 0:
    print(N-1)
else:
    print(a+x-2)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
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

a = make_divisors(N)
if len(a)%2 == 1:
  print(2*int(math.sqrt(N))-2)
else:
  b = a[len(a)/2-1]
  c = a[len(a)/2]
  print(b+c-2)

Submission status: Runtime Error

Solution code:
n = int(input())

a_list = []
b_list = []
start = 1
for i in range(1,int(n/2)):
  if i * i > n:
    start = i
b = 0
for a in range(1,start):
  if n % a == 0:
    b = n / a
  a_list.append(int(a)-1)
  b_list.append(int(b)-1)

sum_list = []
for a,b in zip(a_list,b_list):
  sum_list.append(a+b)
print(int(min(sum_list)))

Submission status: Runtime Error

Solution code:
import math
a,b,x = map(int, input().split())

if x >= (a * a * b) / 2:
	c = 2 * b - (2 * x) / (a * a)
	angle = math.degrees(math.atan(c / a))
else:
	d = x / (a * b)
	angle = math.degrees(math.atan(b / d))
print(angle)

Submission status: Runtime Error

Solution code:
N = int(input())
rt = int(math.sqrt(N))

a = rt
while a>0:
    x = N/a
    if x.is_integer():
        x = int(x)
        break
    a = a-1

if a == 0:
    print(N-1)
else:
    print(a+x-2)

Submission status: Runtime Error

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

n = int(input())
s = factorization(n) 
 
s_ = []
for i in range(len(s)):
    for j in range(s[i][1]):
        s_.append(s[i][0])

a = []
b = []

for i in range(len(s_)//2):
    c = list(itertools.combinations(s_,i+1))
    for j in range(len(c)):
        d = list(c[j])
        p = np.prod(d)
        a.append(p)
        b.append(n/p)

m = 10000000000000

for i in range(len(a)):
    m = min(m,a[i]+b[i]-2)
print(int(m))

Submission status: Runtime Error

Solution code:

from functools import reduce
from operator import mul
from collections import Counter

def prod(arr):
    return reduce(mul, arr, 1)

def fancy(arr, index):
    output = []
    for i, v in enumerate(index):
        if v:
            output.append(arr[i])
    return output

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

N=int(input())
factors = prime_factorize(N)
counter = Counter(factors)
odd_factors = [factor for factor in factors if counter[factor]%2!=0]
even_factors = [factor for factor in factors if counter[factor]%2==0]
N_odd = prod(odd_factors)

selectors = [list(map(bool, map(int, list("{0:b}".format(i).zfill(len(odd_factors)))))) for i in range(1, 2**len(odd_factors))]
even_coeff = prod(even_factors[::2])

combinations = [(prod(fancy(factors, selector))*even_coeff, even_coeff*N_odd//prod(fancy(factors, selector))) for selector in selectors]

distances = [combination[0]-1 + combination[1]-1 for combination in combinations]
print(min(distances))

Submission status: Runtime Error

Solution code:
N = input()
rt = int(math.sqrt(N))
print(rt)
a = rt
while a>0:
    x = N/a
    if x.is_integer():
        x = int(x)
        break
    a = a-1

if a == 0:
    print(N-1)
else:
    print(a+x-2)

Submission status: Runtime Error

Solution code:
N = int(input())
rt = int(math.sqrt(N))
print(rt)
a = rt
while a>0:
    x = N/a
    if x.is_integer():
        x = int(x)
        break
    a = a-1

if a == 0:
    print(N-1)
else:
    print(a+x-2)

Submission status: Runtime Error

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

Submission status: Runtime Error

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)

serch_mini.remove(bb+cc)

print(min(serch_mini)-2)

Submission status: Runtime Error

Solution code:
n = int(input())
# divisors = []
move =[]
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
#         divisors.append(i)
        move.append(i+n//i)
        if i != n // i:
            divisors.append(n//i)
        
# divisors.sort()
# print(divisors)
# print(move)
print(min(move)-2)

Submission status: Runtime Error

Solution code:
import math
N = int(input()) 
factor = []
tmp = int(math.sqrt(N)) + 1
print(tmp)
list = range(2,tmp)
print(list[::-1])
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)
        print("N="+str(N))
    else:
        pass
    break
f=factor[0]+factor[1]-1
print(f)
18

Submission status: Runtime Error

Solution code:
N = int(input())
import math
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
if is_prime(N):
  print(N-1)
else:
  a = np.floor(math.sqrt(N))
  while True:
    if N%a==0:
      break
      a=a-1
      b=N/a
      print(int(a+b-2))

Submission status: Runtime Error

Solution code:
import math

n = int(input())
n_h = n+1 // 2

yakusu = []
for i in range(1, n_h):
    if n % i == 0:
        yakusu.append(i)

l = len(yakusu) -1
half = l // 2

ans = yakusu[half] + yakusu[half+1] - 2

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
divide = []
for i in range(2,int( (10**6) ) + 1):
    while( N % i == 0):
        divide.append(i)
        N = int( N/i )
    if N ==1:
        break

i = 0
check = []
while(i < len(divide)-1):
    x = 1
    a = divide[:i+1]
    for j in a:
        x= x * j
    b = divide[i+1:]
    y = 1
    for j in b:
        y = y * j
    check.append(x + y)
    i += 1
    
ans = min(check) - 2
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())

a_list = []
b_list = []
start = 1
for i in range(1,int(n/2)):
  if i * i > n:
    start = i
b = 0
for a in range(i,n+1):
  if n % a == 0:
    b = n / a
  a_list.append(int(a)-1)
  b_list.append(int(b)-1)

sum_list = []
for a,b in zip(a_list,b_list):
  sum_list.append(a+b)
print(int(min(sum_list)))

Submission status: Runtime Error

Solution code:
A,B,X=map(int, input().split())
C=2*X/(A*B)
if C<=A:
    math.atan(B/C)*(180)/math.pi
    C=2*X/(A*B)
    print(math.atan(B/C)*(180)/math.pi)
else:
    C=2*Y/(A*A)
    Y=A*A*B-X
    C=2*Y/(A*A)
    print(math.atan(C/A)*(180)/math.pi)

Submission status: Runtime Error

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) and len(a) > 1:
  prev_result = prod(a) + prod(b)
  b.append(a.pop(a.min()))

try:
  if prev_result < prod(a) + prod(b) and len(b) > 1:
    a.append(b.pop(b.min()))

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

Submission status: Runtime Error

Solution code:
N = int(input())
divide = []
for i in range(2,int( (10**12) ** (1/ 2) ) + 1):
    while( N % i == 0):
        divide.append(i)
        N = int( N/i )
    if N ==1:
        break

i = 0
check = []
while(i < len(divide)-1):
    x = 1
    a = divide[:i+1]
    for j in a:
        x= x * j
    b = divide[i+1:]
    y = 1
    for j in b:
        y = y * j
    check.append(x + y)
    i += 1
    
ans = min(check) - 2
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul
N = int(input())
divide = []
for i in range(2,int( (10**12) ** (1/ 2) ) + 1):
    while( N % i == 0):
        divide.append(i)
        N = int( N/i )
    if N ==1:
        break

i = 0
check = []
while(i < len(divide)-1):
    x = 1
    a = divide[:i+1]
    for j in a:
        x= x * j
    b = divide[i+1:]
    y = 1
    for j in b:
        y = y * j
    check.append(x + y)
    i += 1
    
ans = min(check) - 2
print(ans)

Submission status: Runtime Error

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


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


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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i, n) for(int i=1; i<=n; i++)
using namespace std;
int main(void){
    long n;
    long ans=1000000000002;
    cin >> n;
    rep(i, n){
        for(int j=i; j<=n/i; ++j){
            if(i*j==n and ans >i+j-2) ans = i+j-2;
        }
    }
    cout << ans << endl;
}