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

# 因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a = prime_factorize(N)
if len(a) == 1:
    print(N-1)
else:
    minAns = float('inf')
    for i in range(1 << len(a)):
        x = 1
        y = 1
        for j in range(len(a)):
            if (i >> j) & 1 == 1:
                x *= a[j]
            else:
                y *= a[j]
        if x-1 + y-1 < minAns:
            minAns = x-1 + y-1
    print(minAns)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
ans = 10**12

for k in range(1,n+1//2):
    if n%k == 0 :
        m = n//k + k - 2
        if ans > m:
            ans = m
        else:
            print(ans)
            sys.exit()
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

L=make_divisors(N)
ans=float("INF")
for n in L:
    for k in L:
        if n*k==N:
            ans=min(ans, n+k-2)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tmp = 1
 
for i in range(1,10**10):
  if n%i == 0:
    if i <= n//i:
      tmp  = i
    else:
      break
  elif tmp == 1 and i >= n/i:
    break
    
   
    
      
print(tmp + (n//tmp) -2)

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

n = ni()
nn = n
mn = 10**12
nums = [1]

i=2
while i<=math.ceil(math.sqrt(n)+1):
  while n%i==0:
    nums.append(i)
  i+=1

for num in nums:
  other = nn//num
  mn = min(mn, num+other-2)

print(mn)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# C - Walk on Multiplication Table
# https://atcoder.jp/contests/abc144/tasks/abc144_c

n = int(input())

comb=[]

# i*j=n となる組み合わせを算出
for i in range(1,n+1):
    for j in range(1,n+1):
         if n == (i*j):
             comb.append((i-1)+(j-1))
# その中で最小のものを出力
print(sorted(comb)[0])

Submission status: Time Limit Exceeded

Solution code:
#ABC 144 C - Walk on Multiplication Table
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
from itertools import combinations
import functools
import operator
P = prime_factorize(N)
m = N+1
memo = []
for i in range(1,len(P)+1):
    L1 = list(combinations(P,i))
    L1 = [list(l) for l in L1]
    for l in L1:
        if l not in memo:
            memo.append(l)
            s1 = functools.reduce(operator.mul,l)
            s2 = N/s1
            if s1+s2 <=m:
                m = s1+s2
print(int(m-2))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
 
list=[]
 
for i in range(1,n+1):
    if len(list) == 1 and i>int(n/i):
        ans=(list[-1][0]-1)+(list[-1][1]-1)
        break
    a=n%i

    if a == 0:
        if(i<n/i):
            list.append([i,int(n/i)])
            if list[-1][0] == list[-1][1]:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
        else:
            list.append([int(n/i),i])
            if len(list) == 1:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
                break
            if list[-1]==list[-2]:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
 
list=[]
 
for i in range(1,n+1):
    if len(list) == 1 and i>int(n/i):
        ans=(list[-1][0]-1)+(list[-1][1]-1)
        break
    a=n%i
    if a == 0:
        if(i<n/i):
            list.append([i,int(n/i)])
        else:
            list.append([int(n/i),i])
            if len(list) == 1:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
                break
            if list[-1]==list[-2]:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

list=[]

for i in range(1,n+1):
    a=n%i
    if a == 0:
        if(i<n/i):
            list.append([i,int(n/i)])
        else:
            list.append([int(n/i),i])
            if len(list) == 1:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
                break
            if list[-1]==list[-2]:
                ans=(list[-1][0]-1)+(list[-1][1]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

list=[]

for i in range(1,n+1):
    a=n%i
    if a == 0:
        if(i<n/i):
            list.append([i,int(n/i)])
        else:
            list.append([int(n/i),i])
            if i>1 :
                if len(list) == 1:
                    ans=(list[-1][0]-1)+(list[-1][1]-1)
                    break
                if list[-1]==list[-2]:
                    ans=(list[-1][0]-1)+(list[-1][1]-1)
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
def factorization(num):
    result = []
    temp = num
    for i in range(2, int(num ** 0.5) + 1):
        while temp % i == 0:
            temp = int(temp / i)
            result.append(i)

    if temp != 1:
        result.append(temp)
    if result == []:
        result.append(num)
    return result
factors = factorization(n)
ans = 1000000000000
for i in range(2 ** len(factors)):
    f0, f1 = 1, 1
    for j in range(len(factors)):
        if i >> j & 1:
            f1 *= factors[j]
        else:
            f0 *= factors[j]
    ans = min(ans, f0 + f1 - 2)
print(ans)

Submission status: Time Limit Exceeded

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

# check
all_case = [
    sum((i - 1, N // i - 1))
    for i in range(1, N + 1, 1)
    if N % i == 0
]

print(min(all_case))

Submission status: Time Limit Exceeded

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

# check
all_case = [
    sum((i - 1, j - 1))
    for i in range(1, N + 1, 1)
    for j in range(1, N + 1, 1)
    if i * j == N
]

print(min(all_case))

Submission status: Time Limit Exceeded

Solution code:

# 素因数分解（辞書型で返ってくるので今回は使いにくい）
"""
pf={}
n = int(input())
for i in range(2,int(n**0.5)+1):
    while n % i == 0:
        pf[i] = pf.get(i,0)+1
        n//= i
if n > 1 : pf[n] = 1
print(pf)
"""
"""
# Return a list of the prime factors for a natural number bigger than 1
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

n = int(input())
# print(trial_division(n)) # 結果がリストで返ってくる
"""

n=int(input())

for i in range(1,10000):
    for j in range(1,i+1):
        seki=i*j
        if seki==n:
            print(i+j-2)
            exit()

Submission status: Time Limit Exceeded

Solution code:

# 素因数分解（辞書型で返ってくるので今回は使いにくい）
"""
pf={}
n = int(input())
for i in range(2,int(n**0.5)+1):
    while n % i == 0:
        pf[i] = pf.get(i,0)+1
        n//= i
if n > 1 : pf[n] = 1
print(pf)
"""
"""
# Return a list of the prime factors for a natural number bigger than 1
def trial_division(n):
    if n < 2:
        return []

    prime_factors = []

    for i in range(2, int(n**0.5)+1):
        # nがi（の累乗）で割り切れるかを調べる
        while n % i == 0:
            # nがiで割り切れる場合、iを素因数としてリストに追加する
            prime_factors.append(i)
            # nをiで割った商で更新しておく
            n //= i
    # nの平方根より大きい素因数が存在する場合
    if n > 1:
        prime_factors.append(n)

    return prime_factors

n = int(input())
# print(trial_division(n)) # 結果がリストで返ってくる
"""

n=int(input())

for i in range(1,100000):
    for j in range(1,i+1):
        seki=i*j
        if seki==n:
            print(i+j-2)
            exit()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
l = []
for it in itertools.combinations_with_replacement(divisor(n),2):
    if it[0] * it[1] == n:
        l.append(it[0] + it[1] -2)
print(sorted(l)[0])

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
l = float("inf")
for it in itertools.combinations_with_replacement(divisor(n),2):
    if it[0] * it[1] == n:
        l = min(it[0] -1 + it[1] -1,l)
print(l)

Submission status: Time Limit Exceeded

Solution code:
from math import *

n= int(input())
val = floor(sqrt(n))
a = []
for i in range(val,n):
    if n%i == 0:
        a.append([i,n//i])
        break

print(a[0][0]+a[0][1]-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
    
A = prime_factorize(N)
L = []
for i in range(1<<len(A)):
    tmp = 1
    j = bin(i)[2:]
    leng = len(j)
    for k in range(leng):
        if j[leng-k-1]=="1":
            tmp *= A[k]
    L.append(tmp)
    
ans = []
for i in L:
    j = N//i
    ans.append(i+j-2)
    
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
from math import sqrt
root = int(sqrt(n))

for i in range(root,n+1):
    if n%i == 0:
        ans = i+(n/i)-2
        break
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

from itertools import combinations
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)
    return divisors

d=make_divisors(N)

if math.sqrt(N)**2 ==N:
    d.append(int(math.sqrt(N)))

c= list(combinations(d,2))

# Candidate = [n for n in c if n[0]*n[1]==N]        

# # for n in c:
#     # if n[0]*n[1]==N:
#     #     Candidate.append(n)

dist=float('inf')

for i in c:
    if i[0]*i[1]==N:
        dist = min(dist,i[0]+i[1]-2)

print(dist)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

from itertools import combinations
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)
    return divisors

d=make_divisors(N)

if math.sqrt(N)**2 ==N:
    d.append(int(math.sqrt(N)))

c= list(combinations(d,2))

Candidate = [n for n in c if n[0]*n[1]==N]        

# for n in c:
    # if n[0]*n[1]==N:
    #     Candidate.append(n)

dist=float('inf')
for i in Candidate:
    dist = min(dist,i[0]+i[1]-2)

print(dist)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

from itertools import combinations
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

d=make_divisors(N)

if math.sqrt(N)**2 ==N:
    d.append(int(math.sqrt(N)))

c= list(combinations(d,2))

Candidate = []        

for n in c:
    if n[0]*n[1]==N:
        Candidate.append(n)

dist=float('inf')


for i in Candidate:
    dist = min(dist,i[0]+i[1]-2)

print(dist)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
def is_prime(num):
    import math
    if num == 2:
        return True
    elif num <  3 or num % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

if is_prime(n):
    print(n-1)
    exit()

ans = float('inf')
for i in range(n//2, 0, -1):
    if n%i == 0:
        ans = min(ans, (i-1)+(n//i-1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

import math

for i in range(int(math.sqrt(N)), N):
    if N % i == 0:
        print(i-1 + int(N / i) -1)
        break

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)
l=len(A)

res=10**13
for i in range(2**l):
	cnt=1
	for j in range(l):
		if (i>>j)&1:
			cnt *= A[j]
	cnt = n//cnt + cnt
	res=min(cnt,res)
print(res-2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
pf={}
res = []
m= int(input())
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        res.append(i)
        m//=i
if m>1:
    res.append(m)
    pf[m]=1

cgg = deque()
for index in range(2**len(res)):

    s1 = 1
    s2 = 1
    for j in range(len(res)):
        if (index >> j & 1) == 1:
            s1 = s1 * res[j]
        else:
            s2 = s2 * res[j]

    cgg.append(s1-1 + s2 - 1)


print(min(cgg))

Submission status: Time Limit Exceeded

Solution code:
pf={}
res = []
m= int(input())
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        res.append(i)
        m//=i
if m>1:
    res.append(m)
    pf[m]=1

cgg = []
for index in range(2**len(res)):

    s1 = 1
    s2 = 1
    for j in range(len(res)):
        if (index >> j & 1) == 1:
            s1 = s1 * res[j]
        else:
            s2 = s2 * res[j]

    cgg.append(s1-1 + s2 - 1)


print(min(cgg))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

r=[]

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

print(min(r))

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

prime_L = prime_factorize(N)
n = len(prime_L)
sum = 10 ** 13

for i in range(2 ** n):
    bit = str(format(i, 'b')).zfill(n)
    total_a = 1
    total_b = 1
    for j in range(n):
        if bit[j] == '0':
            total_a = total_a * prime_L[j]
        elif bit[j] == '1':
            total_b = total_b * prime_L[j]
    if total_a + total_b - 2 < sum:
        sum = total_a + total_b - 2
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
if n >= 2:
     prime_nums = [2]
     for i in range(3, n + 1):
         for p in prime_nums:
             if i % p == 0:
                 break
         else:
             prime_nums.append(i)
for x in prime_nums[::-1]:
    if n % x == 0:
        print(x + n//x - 2)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n = int(input())
i = floor(sqrt(n))
dis = 0
while True:
    f = i / n
    j = floor(f)
    if f - j > 0:
        dis += 1
        continue
    print(i + j)
    sys.exit()

Submission status: Time Limit Exceeded

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

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

l = prime_factorize(N)
ans = 10 ** 12
for i in range(2**len(l)):
    a = 1
    b = 1
    for j in range(len(l)):
        if (i>>j & 1):
            a *= l[j]
        else:
            b *= l[j]
    if ans > a - 1 + b - 1:
        ans = a - 1 + b - 1
    
print(ans)

Submission status: Time Limit Exceeded

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 accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = []
for i in range(1, -(-N//1)):
  if N%i == 0:
    A.append(i + N//i -2)

print(min(A))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

import math
i = int(math.sqrt(N))

while True:
    if N%i == 0:
        ls = [i,int(N//i)]
        break
    i+=1
print(sum(ls)-2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

m = len(divisors)

a = divisors[m//2-1]
b = divisors[m//2]

print(a+b-2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

import math
a = int(math.sqrt(n))

for i in range(a,n+1):
  if n%i == 0:
    move = (i-1) + int(n/i)-1
    print(move)
    exit()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools


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


n = int(readline())
memo = prime_decomposition(n)
ans = float('inf')
if len(memo) == 1:
    print(memo[0] - 1)
else:
    len_memo = len(memo)
    bit = list(itertools.product([0, 1], repeat=len_memo))
    for i in range(2 ** len_memo):
        x, y = 1, 1
        for j in range(len_memo):
            if bit[i][j] == 0:
                x *= memo[j]
            else:
                y *= memo[j]
        if ans > x + y - 2:
            ans = x + y - 2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools


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


n = int(readline())
memo = prime_decomposition(n)
ans = float('inf')
if len(memo) == 1:
    print(memo[0] - 1)
else:
    bit = list(itertools.product([0, 1], repeat=len(memo)))
    for i in range(2 ** len(memo)):
        x, y = 1, 1
        for j in range(len(memo)):
            if bit[i][j] == 0:
                x *= memo[j]
            else:
                y *= memo[j]
        if ans > x + y - 2:
            ans = x + y - 2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
divisors = []
for i in range(1, int(pow(n, 0.5)) + 1):
    if n % i == 0:
        divisors.append([i, n // i])
    divisors = sorted(divisors, key= lambda x:x[1])
res = 0
for i in divisors[0]:
    res += i - 1

print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

def dfs(a, x, y):
  if len(x)+len(y)==len(a):
    if len(x)==0 or len(y)==0:
      a_ = a[0]
      for i in range(1, len(a)):
        a_ *= a[i]
      return a_ + 1
    else:
      x_ = x[0]
      y_ = y[0]
      for i in range(1, len(x)):
        x_ *= x[i]
      for i in range(1, len(y)):
        y_ *= y[i]
      return x_ + y_
  res1 = dfs(a, x + [a[len(x)+len(y)]], y)
  res2 = dfs(a, x, y + [a[len(x)+len(y)]])
  return min(res1, res2)

n = int(input())
primes = prime_factorize(n)
print(dfs(primes, [], [])-2)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())

List = []
for i in range(1,10**4):
    for j in range(1,10**4):
        if N == i*j:
            List.append(i+j)

print(min(List)-2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

List = []
for i in range(1,10**5):
    for j in range(1,10**5):
        if N == i*j:
            List.append(i+j)

print(min(List)-2)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lst=[]
for i in range(1,n):
    #if i**2>n:
    #    break
    if n%i==0:
        lst.append(i+n//i)
print(min(lst)-2)

Submission status: Time Limit Exceeded

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

for i in range(1,num+1):
    if num % i == 0:
        list.append((i-1)+(num/i)-1)
    else:
        None

list.sort()
print(round(list[0]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
for i in range(1, n + 1):
    if n % i == 0:
        if i ** 2 > n:
            break
        j = n // i
        l.append(i + j)

print(min(l) - 2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
for i in range(1, n + 1):
    if n % i == 0:
        j = n // i
        l.append(i + j)

print(min(l) - 2)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())

list = []



for x in range(1,num+1):
    for i in range(num+1):
        if x * (x+i) == num:
            if x + x+i == 2:
                print("0")

            else:
                list.append((x-1)+(x+i-1))
        else:
            None


list.sort()
print(list[0])

Submission status: Time Limit Exceeded

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


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

N = int(input())
factors = trial_division(N)

if len(factors) == 1:
  print(factors[0]-1)
else:
  res = N
  cumsum = reduce(mul, factors)
  for i in range(len(factors)//2):
    for comb in itertools.combinations(factors, i+1):
      a = reduce(mul, comb)
      b = cumsum // a
      if a+b-2 < res:
        res = a+b-2
  print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = 1
x = []
y = []
for i in range(1, n+1):
  if n % (k*i) == 0:
    x.append(k*i)
    y.append(n//(k*i))
    if n // (k*i) < k*i:
      break

print(x[len(x)-2] + y[len(x)-2] -2)

Submission status: Time Limit Exceeded

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

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

primes = prime_factorize(N)
prod = np.prod(np.array(primes))
index = [i for i in range(len(primes))]
ans = prod - 1

for i in range(1, len(primes) // 2 + 1):
    for cmb in itertools.combinations(index, i):
        i_next = np.prod(np.array([primes[c] for c in cmb]))
        j_next = prod // i_next
        ans = min(ans, i_next + j_next - 2)
            
print(ans)

Submission status: Time Limit Exceeded

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

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

primes = prime_factorize(N)
prod = np.prod(np.array(primes))
index = [i for i in range(len(primes))]
ans = prod - 1

for i in range(1, len(primes)):
    for cmb in itertools.combinations(index, i):
        i_next = np.prod(np.array([primes[k] for k in range(len(primes)) if k in cmb]))
        j_next = prod // i_next
        ans = min(ans, i_next + j_next - 2)
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  t=0
  for x in range(1,n+1):
    for y in range(1,x+1):
      if x*y==n:
        return x+y-2

if __name__ == '__main__':
  print(main())

Submission status: Time Limit Exceeded

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

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

primes = prime_factorize(N)
index = [i for i in range(len(primes))]
ans = False

for i in range(1, len(primes) // 2 + 1):
    for cmb in itertools.combinations(index, i):
        if i != len(primes):
            i_moved = np.prod(np.array([primes[k] for k in range(len(primes)) if k in cmb])) - 1
            j_moved = np.prod(np.array([primes[k] for k in range(len(primes)) if k not in cmb])) - 1 
        else:
            i_moved = np.prod(np.array(primes)) - 1
            j_moved = 0
        if ans is not False:
            ans = min(ans, i_moved + j_moved)
        else:
            ans = i_moved + j_moved
            
print(ans)

Submission status: Time Limit Exceeded

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

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

primes = prime_factorize(N)
index = [i for i in range(len(primes))]
ans = False

for i in range(1, len(primes) + 1):
    for cmb in itertools.combinations(index, i):
        if i != len(primes):
            i_moved = np.prod(np.array([primes[k] for k in range(len(primes)) if k in cmb])) - 1
            j_moved = np.prod(np.array([primes[k] for k in range(len(primes)) if k not in cmb])) - 1 
        else:
            i_moved = np.prod(np.array(primes)) - 1
            j_moved = 0
        if ans is not False:
            ans = min(ans, i_moved + j_moved)
        else:
            ans = i_moved + j_moved
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
i,j=1,1
C=[(i,j)]
while True:
    p=C.pop(0)
    i,j=p[0],p[1]
    if p[0]*p[1]==N:
      print(p[0]+p[1]-2)
      break
    else:
      C.append((i,j+1))
      if i+1==j:
        C.append((i+1,j))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
i,j=1,1
C=[(i,j)]
while True:
    p=C.pop(0)
    if p[0]*p[1]==N:
      print(p[0]+p[1]-2)
      break
    else:
      C.append((i+1,j))
      C.append((i,j+1))
      i+=1
      j+=1

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []

# 二つの掛け算の組み合わせを列挙
for n in range(1, int(N/2) + 1):
  if N % n == 0:
    a.append( int(n + N/n) )

# その中で一番足した数が少ないものを選択する
print(min(a) - 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.readline().rstrip())

    ret = float('inf')
    for i in range(1, 100000000):
        q, mod = divmod(N, i)
        if mod == 0:
            j = N // i
            ret = min(ret, ((j-1)+(i-1)))

    print(ret)


if __name__ == '__main__':
    main()