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: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
import itertools

N = int(input())

# N = i*jをみつける
# (i, j)


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

prime_list = prime_factorize(N)


#print(prime_list)


import copy
if len(prime_list)<=1:
    result = N-1
else:
    result = 10**12

for i in range(len(prime_list)//2):
    # i個抽出
    tmp = list(itertools.combinations(prime_list, i+1))
    tm = map(list, tmp)
    for _ in tm:
        temp_origin_list = copy.copy(prime_list)
        for item in _:
            temp_origin_list.remove(item)
        #print(_, temp_origin_list)
        result = min(result, reduce(mul, _) + reduce(mul, temp_origin_list) - 2)
print(result)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
import itertools

N = int(input())

# N = i*jをみつける
# (i, j)


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

prime_list = prime_factorize(N)


#print(prime_list)


import copy
if len(prime_list)<=1:
    result = N-1
else:
    result = 10**12

for i in range(len(prime_list)//2):
    # i個抽出
    tmp = list(itertools.combinations(prime_list, i+1))
    tm = list(map(list, tmp))
    for _ in tm:
        temp_origin_list = copy.copy(prime_list)
        for item in _:
            temp_origin_list.remove(item)
        #print(_, temp_origin_list)
        result = min(result, reduce(mul, _) + reduce(mul, temp_origin_list) - 2)
print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 10**12
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

q = factorization(n)
ans_list = []
for i in range(len(q)):
    for j in range(q[i][1]):
        ans_list.append(q[i][0])

p = 1
for i in ans_list:
    p *= i
s = len(ans_list)
for i in range(2 ** s):
    bag = []
    for j in range(s):
        if ((i >> j) & 1): 
            bag.append(ans_list[j]) 
    a = 1
    for t in bag:
        a *= t
    b = p/a
    
    ans = min(ans,a+b-2)
    
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 10**12
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

q = factorization(n)
ans_list = []
for i in range(len(q)):#分解してリストに一つずつ格納
    for j in range(q[i][1]):
        ans_list.append(q[i][0])

if len(ans_list) == 1:
    print(ans_list[0]-1)
    exit()
        
ans_list = sorted(ans_list,reverse = True)#最小となるようにソートして掛けていく
p = 1
for i in ans_list:
    p *= i
s = len(ans_list)
for i in range(2 ** s):
    bag = []
    for j in range(s):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(ans_list[j]) 
    a = 1
    for t in bag:
        a *= t
    b = p/a
    
    ans = min(ans,a+b-2)
    
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
m = math.sqrt(n)
m = int(n + 1)
ans = []
for i in range(m):
    for j in range(m):
        if i * j == n:
            ans.append(i+j-2)
print(min(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

def factorization(n):
    '''
    素因数分解の結果を返す
    例： n = 100 の時、[2, 2, 5, 5] 
    '''
    arr = []
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            while tmp % i == 0:
                arr.append(i)
                tmp //= i
    if tmp != 1:
        arr.append(tmp)
    if arr == []:
        arr.append(n)
    return arr


def combination(l):
    res = []
    for i in range(1, 2**len(l)):
        tmp = []
        for j in range(len(l)):
            if (i >> j) &1 == 1:
                tmp.append(l[j])
        res.append(tmp)
    return res


def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


def solve():
    N = int(input())
    F = factorization(N)
    ans = N - 1
    for c in get_unique_list(combination(F)):
        t = reduce(lambda x, y: x * y, c)
        ans = min(ans, N // t - 1 + t - 1)
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

def factorization(n):
    '''
    素因数分解の結果を返す
    例： n = 100 の時、[2, 2, 5, 5] 
    '''
    arr = []
    tmp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if tmp % i == 0:
            while tmp % i == 0:
                arr.append(i)
                tmp //= i
    if tmp != 1:
        arr.append(tmp)
    if arr == []:
        arr.append(n)
    return arr


def combination(l):
    res = []
    for i in range(1, 2**len(l)):
        tmp = []
        for j in range(len(l)):
            if (i >> j) &1 == 1:
                tmp.append(l[j])
        res.append(tmp)
    return res


def solve():
    N = int(input())
    F = factorization(N)
    ans = N - 1
    for c in combination(F):
        t = reduce(lambda x, y: x * y, c)
        ans = min(ans, N // t - 1 + t - 1)
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from copy import copy

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)

    if temp!=1:
        arr.append(temp)

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

    return arr

facts = factorization(N)

def dfs(arr, depth):
    if depth == len(facts):
        left = reduce(lambda a,b: a * b, [f for i, f in enumerate(facts) if arr[i]], 1)
        right = reduce(lambda a, b: a * b, [f for i, f in enumerate(facts) if not arr[i]], 1)
        return left + right
    left_arr = copy(arr)
    left_arr.append(True)
    right_arr = copy(arr)
    right_arr.append(False)
    left = dfs(left_arr, depth+1)
    right = dfs(right_arr, depth + 1)
    return min(left, right)
print(dfs([], 0) - 2)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Sep  9 01:55:56 2020

@author: liang
"""

import math
N = int(input())
key = int(math.sqrt(N))

ans = 10**12
for i in range(1,N+1):
    if N%i == 0:
        tmp = i-1 + N//i -1
        if ans > tmp:
            ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math


def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

n = int(input())
ans = 10**15

if isPrime(n):
    print(n-1)
    exit()
for i in range(10**5+1):
    for j in range(i,10**6+1):
        if i*j == n:
            ans = min(ans,i+j-2)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


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


p = prime_factorize(n)
ans = 10**13
pr0 = 1

for i in range(1, len(p)+1):
    for P in itertools.combinations(p, i):
        pr = 1
        for pp in P:
            pr *= pp
        ans = min(ans, pr+n//pr-2)

print(ans)

Submission status: Time Limit Exceeded

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


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


p = prime_factorize(n)
ans = 10**13
pr0 = 1
for pp in p:
    pr0 *= pp

for i in range(1, len(p)+1):
    for P in itertools.combinations(p, i):
        pr = 1
        for pp in P:
            pr *= pp
        ans = min(ans, pr+pr0//pr-2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
def input():
    return sys.stdin.readline()[:-1]

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

def main():
    N = int(input())

    arr = factorization(N)
    l = []
    for i in arr:
        for j in range(i[1]):
            l.append(i[0])

    A = 10**13
    B = 10**13
    for i in product([0, 1], repeat=len(l)):
        a = 1
        b = 1
        for k in range(len(l)):
            if i[k] == 0:
                a *= l[k]
            if i[k] == 1:
                b *= l[k]
        if a + b < A + B:
            A = a
            B = b
    print(A + B - 2)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
x = int(N**0.5)
ans_1 = N

for i in range(N):
    if N % x == 0:
        ans_1 = x
        break
    else:
        x += 1

ans_2 = N//ans_1
print(ans_1 + ans_2 - 2)

Submission status: Time Limit Exceeded

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

pri_fact=prime_factorize(n)

def prod(x):
    kotae=1
    for i in x:
        kotae*=i
    return kotae

ans=10**120
import itertools

for r in range(len(pri_fact)):
# (1,2,3),(1,2,4),---,(7,8,9)
    for seq in itertools.combinations(range(len(pri_fact)),r):
        a=[1]
        b=[1]
        for i in range(len(pri_fact)):
            if i in seq:
                a.append(pri_fact[i])
            else:
                b.append(pri_fact[i])
        ans=min(prod(a)+prod(b)-2,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
#i+j-2=cnt & i*j=n
import math
minn=100000000000000000000
i=1
while i**2<n:
    if n%i==0:
        j=n/i
        minn=min(int(i+j-2),minn)
print(minn)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
#i+j-2=cnt & i*j=n
import math
minn=10000000000000000
for i in range(1,math.floor(n)):
    if n%i==0:
        j=n/i
        minn=min(int(i+j-2),int(minn))
    else:
        continue
print(minn)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
m = 1
for s in range(1,n+1):
    for t in range(m,n+1):
        if n == s*t:
            l.append((s-1) + (t-1))
    m += 1
print(min(l))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

l = []
for s in range(1,n+1):
    for t in range(1,n+1):
        if n == s*t:
            l.append((s-1) + (t-1))
print(min(l))

Submission status: Time Limit Exceeded

Solution code:
def prime_factors(n):       # 戻り値はiterable type
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i             # whileループを進めるごとにイテレータに値を貯め続ける
    if n > 1:
        yield n

def min2(x,y):
    return x if x < y else y

from itertools import combinations

N = int(input())
P = list(prime_factors(N))
L = len(P) + 1
res =float("inf")

for k in range(L//2, 0, -1):
    for a in combinations(prime_factors(N), k):
        q = 1
        for p in a:
            q *= p
        res = min2((q - 1) + (N // q - 1), res)

print(res)

Submission status: Time Limit Exceeded

Solution code:
def prime_factors(n):       # 戻り値はiterable type
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i             # whileループを進めるごとにイテレータに値を貯め続ける
    if n > 1:
        yield n

def min2(x,y):
    return x if x < y else y

from itertools import combinations

N = int(input())
P = list(prime_factors(N))
L = len(P) + 1
res =float("inf")

for k in range(1, L//2+1):
    for a in combinations(prime_factors(N), k):
        q = 1
        for p in a:
            q *= p
        res = min2((q - 1) + (N // q - 1), res)

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
print

true_ans = 10 ** 12
for i in range(1,N):
    if N % i == 0:
        ans = N // i
        true_ans = min(ans + i - 2, true_ans)
        if(i > N ** 0.5):
            break

print(true_ans)

Submission status: Time Limit Exceeded

Solution code:
# abc144_c.py
# https://atcoder.jp/contests/abc144/tasks/abc144_c

# C - Walk on Multiplication Table /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 高橋君は無限に広い掛け算表の上にいます。
# 掛け算表のマス (i,j)には整数 i×j が書かれており、高橋君は最初 (1,1)にいます。
# 高橋君は 1回の移動で (i,j) から (i+1,j) か (i,j+1)のどちらかにのみ移ることができます。
# 整数 Nが与えられるので、Nが書かれているマスに到達するまでに必要な移動回数の最小値を求めてください。
# 制約
#     2≤N≤1012
#     Nは整数である。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N

# 出力
# 整数 Nが書かれているマスに到達するまでに必要な移動回数の最小値を出力せよ。

# 入力例 1
# 10

# 出力例 1
# 5

# 5回の移動で (2,5) に到達することができます。5 回未満の移動では 10が書かれたマスに到達することは出来ません。

# 入力例 2
# 50

# 出力例 2
# 13

# 13回の移動で (5,10)に到達できます。

# 入力例 3
# 10000000019

# 出力例 3
# 10000000018

# 入出力とも非常に大きな値になる可能性があります。


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    N = int(lines[0])
    # N, M = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    # prime_numbers = get_prime_numbers(N)
    # log(f'prime_numbers=[{prime_numbers}]')

    # 素因数分解
    log(f'N=[{N}]')
    list_split_by_prime_numbers = get_list_split_by_prime_numbers(N)
    log(f'list_split_by_prime_numbers=[{list_split_by_prime_numbers}]')

    min_rate = None
    for i in range(1, 2**len(list_split_by_prime_numbers)):
        x = 1
        y = 1
        pattern = format(int(format(i, 'b')), '0=' + str(len(list_split_by_prime_numbers)))
        log(f'pattern=[{pattern}]')
        for i, char in enumerate(pattern):
            if char == '0':
                x *= list_split_by_prime_numbers[i]
            else:
                y *= list_split_by_prime_numbers[i]
        log(f'x=[{x}], y=[{y}]')
        if x > y:
            rate = x / y
        else:
            rate = y / x
        log(f'rate=[{rate}]')
        if min_rate is None:
            min_rate = rate
            log(f'min_rate=[{min_rate}]')
            result = x + y - 2
            log(f'result=[{result}]')
        elif min_rate > rate:
            min_rate = rate
            log(f'min_rate=[{min_rate}]')
            result = x + y - 2
            log(f'result=[{result}]')


    # 違った。。。
    # min_rate = None
    # for i in range(1, 2**len(prime_numbers)):
    #     x = 1
    #     y = 1
    #     pattern = format(int(format(i, 'b')), '0=' + str(len(prime_numbers)))
    #     for i, char in enumerate(pattern):
    #         if char == '0':
    #             x *= prime_numbers[i]
    #         else:
    #             y *= prime_numbers[i]
    #     if x > y:
    #         rate = x / y
    #     else:
    #         rate = y / x
    #     if min_rate is None:
    #         log(f'x=[{x}], y=[{y}]')
    #         min_rate = rate
    #         result = x + y - 2
    #     elif min_rate > rate:
    #         log(f'x=[{x}], y=[{y}]')
    #         min_rate = rate
    #         result = x + y - 2

    return [result]


def get_prime_numbers(n):
    lst = [2]
    for i in range(3, n+1):
        flag = False
        for item in lst:
            if i % item == 0:
                flag = True
                break
        if flag is False:
            lst.append(i)
    return lst


# 素因数分解(戻り値dict)
# >>> import abc144_c as abc
# >>> abc.get_dict_split_by_prime_numbers(24)
# {2: 3, 3: 1, 5: 0, 7: 0, 11: 0, 13: 0, 17: 0, 19: 0, 23: 0}
def get_dict_split_by_prime_numbers(n):
    prime_numbers = get_prime_numbers(n)
    dic = dict()
    for prime_number in prime_numbers:
        dic[prime_number] = 0
    current = n
    while True:
        for prime_number in prime_numbers:
            if current % prime_number == 0:
                current /= prime_number
                dic[prime_number] += 1
        if current == 1:
            break
    return dic


# 素因数分解(戻り値list)
# >>> import abc144_c as abc
# >>> abc.get_list_split_by_prime_numbers(24)
# [1, 2, 3, 2, 2]
def get_list_split_by_prime_numbers(n):
    prime_numbers = get_prime_numbers(n)
    lst = list()
    lst.append(1)
    current = n
    while True:
        for prime_number in prime_numbers:
            if current % prime_number == 0:
                current /= prime_number
                lst.append(prime_number)
        if current == 1:
            break
    return lst


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['10']
        lines_export = [5]
    if pattern == 2:
        lines_input = ['50']
        lines_export = [13]
    # ☆ここが駄目☆多分、ここだけで6時間くらいかかる。
    if pattern == 3:
        lines_input = ['10000000019']
        lines_export = [10000000018]
        lines_export = [10000000018]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
ans = 0
x = int(math.ceil(math.sqrt(n)))

for i in range(1, x+1):
    j=i
    while i*j<=n:
        if i*j == n and (i+j-2 < ans or ans == 0):
            ans = i+j-2
            break
        j+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
for i in range(2,10**6):
  a=10**20
  for j in range(2,10**6):
    if i*j==N:
      a=min(a,j+i-2)
print(a)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
A = []
for i in range(2,int(math.sqrt(N))+1):
    if N%i == 0:
        for j in range(1,N//2+1):
            if N == i * j:
                A.append(i + j - 2)
if not A:
    print(N-1)
else:
    print(min(A))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

steps = []

for x in range(n):
    if n % (x + 1) == 0:
        steps.append(x + n // (x + 1) - 1)

print(min(steps))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
search_max = int(N)
 
min_number = 10**12
for x in range(1, search_max + 1):
    if N % x == 0:
        y = N // x
        if x + y < min_number:
         
            min_number = x + y
print(min_number-2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
search_max = int(N*N)
 
min_number = 10**12
for x in range(1, search_max + 1):
    if N % x == 0:
        y = N // x
        if x + y < min_number:
         
            min_number = x + y
print(min_number-2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


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

    if temp != 1:
        array.append(temp)

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

    return array


def devide(array, result):
    if array == []:
        return result

    # xに値を掛けた場合
    x_target = devide(array[1:], (result[0] * array[0], result[1]))

    y_target = devide(array[1:], (result[0], result[1] * array[0]))

    if sum(x_target) <= sum(y_target):
        return x_target
    else:
        return y_target


result = devide(make_prime(N), (1, 1))

print(sum(result) - 2)

Submission status: Time Limit Exceeded

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

f = factorization(n)
l = []
for k, v in f:
    l += [k]*v
ans = n-1
for bit in product([True, False], repeat=len(l)):
    down = 1
    right = 1
    for i in range(len(l)):
        if bit[i]:
            down *= l[i]
        else:
            right *= l[i]
    ans = min(ans, down -1 + right - 1)
print(ans)

Submission status: Time Limit Exceeded

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

f = factorization(n)
l = []
for k, v in f:
    l += [k]*v
ans = n-1
for bit in product([True, False], repeat=len(l)):
    down = 1
    right = 1
    for i in range(len(l)):
        if bit[i]:
            down *= l[i]
        else:
            right *= l[i]
    ans = min(ans, down -1 + right - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

#素因数分解
def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


# N=100
N=int(input())

a=1
b=N//a
dis=abs(a-b)

Li=prime_factorization(N)
# print(Li)

for p in range(2**len(Li)):
    bit=[]
    for e in range(len(Li)):
        if (p>>e)&1==1:
            bit.append(1)
        else:
            bit.append(0)
    # print(bit)
        proindex=[]
        for _ in range(len(bit)):
            if bit[_] ==1:
                proindex.append(_)
        _a=1
        for j in range(len(Li)):
            if proindex.count(j)==1:
                _a*=Li[j]
        _b=N//_a
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis
        if _a>N**0.5:
            break
# print(a,b)

print(a-1+b-1)

Submission status: Time Limit Exceeded

Solution code:

#素因数分解
def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


N=int(input())

a=1
b=N//a
dis=abs(a-b)

Li=prime_factorization(N)
# print(Li)

for p in range(2**len(Li)):
    bit=[]
    for e in range(len(Li)):
        if (p>>e)&1==1:
            bit.append(1)
        else:
            bit.append(0)
    # print(bit)
        proindex=[]
        for _ in range(len(bit)):
            if bit[_] ==1:
                proindex.append(_)
        _a=1
        for j in range(len(Li)):
            if proindex.count(j)==1:
                _a*=Li[j]
        _b=N//_a
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis
# print(a,b)
print(a-1+b-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import math
N = int(input())

def divisor(N):
    lst = []
    for i in range(2,N):
        if N%i == 0:
            lst.append(i)
    #print(lst)
    if len(lst)%2 == 0:
        middle = int(len(lst) / 2)
        #print(lst[middle])
        return lst[middle]
    else:
        middle = int(len(lst) / 2)
        #print(lst[middle])
        return lst[middle]

    
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True
  
if isPrime(N):
    print(N-1)
else:
    ans = divisor(N)
    A = ans
    B = N/ans
    print(int(A+B-2))#
#print(ans)

Submission status: Time Limit Exceeded

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

n = int(input())
a = 1
b = 1
tmp_ans = 0
ans = 10**10

if is_prime(n) == True:
    print(n - 1)
elif is_prime(n) == False:
    for i in range(2, n):
        j = n // i
        if n == i*j:
            tmp_ans = (i-a) + (j-b)
            if tmp_ans < ans:
                ans = tmp_ans
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
for i in range(1, n // 2 + 1):
  if n % i == 0:
    a = i
    b = n // i
    l.append(a + b - 2)
print(min(l))

Submission status: Time Limit Exceeded

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

n=int(input())
a=prime_factorize(n)
x=len(a)
m=float("inf")
for bit in range(1<<x-1):
    ai=1
    bi=1
    for i in range(x):
        if bit&(1<<i):
            ai*=a[i]
        else:
            bi*=a[i]
    m=min(m,ai+bi-2)
print(m)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
res1=0
res2=0
ans=float("INF")
for i in range(1,n+1):
    if n%i==0:
        res1=i
        res2=n/i
        ans=min(ans,res1+res2)
print(int(ans-2))

Submission status: Time Limit Exceeded

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

def factorization(n):
    res = []
    x = N
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)

    return res

ns = factorization(N)

ans = 10**12 + 1
for i in range(1, len(ns)+1):
    for j in itertools.combinations(ns, i):
        val1 = np.prod(j)
        val2 = N // val1
        ans = min(ans, val1+val2-2)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

A=[]

for i in range(1,N+1):
  if N % i ==0:
    A.append(i)

base = int(len(A)/2)

print(A[base]-1 +A[base-1] -1)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc144/tasks/abc144_c C - Walk on Multiplication Table
N=int(input())
S_List = [i for i in range(1,int(N/2)+1) if N % i ==0]
S_List.append(N)
R_S_List = S_List[::-1]

Answer=(10**6)*2
for i in range(len(S_List)):
    Current_Answer = S_List[i] + R_S_List[i] - 2
    if Current_Answer < Answer:
        Answer = Current_Answer

print(Answer)

Submission status: Time Limit Exceeded

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

ans = list()
for i in range(1, int(math.sqrt(N)+1)):
    for j in range(1, N+1): 
        if i * j == N:
            ans.append(i + j -2) 
        else:
             pass

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ans = list()
for i in range(1, N+1):
    for j in range(1, N+1): 
        if i * j == N:
            ans.append(i + j -2) 
        else:
             pass

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
b = np.sqrt(N)//1.0
while True:
    if N%b != 0:
        b -= 1
    else:
        break
print(int(b+N/b-2))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
sqrtN = n**(1/2)
if sqrtN.is_integer():
    Pos = [int(sqrtN), int(sqrtN)]
else:
    for i in range(int(sqrtN), n+1):
        if n%i == 0:
            Pos = [i, n//i]
            break
print(sum(Pos) - 2)