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

last_num = n // 2 + 1

can_division = []
for i in range(1, last_num):
    if n%i == 0:
        can_division.append(i)
can_division.extend([n])

can_division_sorted = can_division[::-1]

sum_num = []
for i in range(len(can_division)):
    sum_num.append((can_division[i]-1) + (can_division_sorted[i]-1))
print(min(sum_num))

Submission status: Time Limit Exceeded

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

def main():
    Input = [input() for i in range(1)]
    N = int(Input[0])
    fact = factorization(N)
    ff = []
    for fn in fact:
        for i in range(fn[1]):
            ff.append(fn[0])
    ans = 10000000000000
    fN = len(ff)
    for wake in range(2**(fN-1)):
        wake2 = format(wake, '0'+str(fN-1)+'b')
        A = ff[-1]
        for i in range(fN-1):
            if wake2[i] == '1':
                 A = A*ff[i]   
        B = N / A
        if A + B - 2 < ans:
            ans = int(A+B-2)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def prime_factorization(n):
    factor = []
    f = 2
    while f ** 2 <= n:
        if n % f == 0:
            factor.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        factor.append(n)
    return factor

p = prime_factorization(N)
from itertools import combinations as cb
from functools import reduce
from operator import mul

s = N+1
for i in range(1, len(p)//2+2):
    for j in cb(p, i):
        A = reduce(mul, j)
        B = N//A
        s = min(s, A+B)

print(s-2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import itertools

n = int(input())

def is_prime(n):
    for p in range(2, n):
        if n % p == 0:
            return 0
    return 1

a = is_prime(n)
if a == 1:
    print(n-1)
    sys.exit()

l = []
for i in range(2, n):
    for j in range(2, n):
        if i*j == n:
            l.append((i-1)+(j-1))
        else:
            continue

print(min(l))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = n

for num in range(1, n + 1):
  if n % num == 0:
    data_x = n / num
    data_y = num
    new = data_x + data_y - 2

    if new < ans:
      ans = new

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
list=[ ]

for i in range(1,math.floor(n*0.5)+1):
  if float(n/i).is_integer()==True:
    j=n/i
    list.append(i+j)

print(int(min(list)-2))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
min = N
max_i = 0
max_j = 0
for i in range(1,N):
    if N % i == 0:
        j = N // i
        if abs(i - j) < min:
            min = abs(i - j)
            max_i = i
            max_j = j

print(max_i + max_j - 2)

Submission status: Time Limit Exceeded

Solution code:
# ABC144 C
from itertools import combinations
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

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

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

    return retlist

N = ni()

ans = 0
L = []
L = factorize(N)

ans = 10**13

for i in range(1,len(L)+1):
    C = []
    C = list(combinations(L,i))
    for c in C:
        a,b = 1,0
        for j in range(len(c)):
            a *= c[j]
            b = N//a
            ans = min(ans,a-1+b-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = N -1

for i in range(1, N//4+1):
    # print(i)
    if N % i == 0:
        ans = min(ans, i+N//i-2)
        # print(ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

for i in range(1,1000000):
    for j in range(1,i+1):
        if (i*j) == N:
            break
    else:
        continue
    break

ans = i + j - 2

print(ans)

Submission status: Time Limit Exceeded

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

def main():
    Input = [input() for i in range(1)]
    N = int(Input[0])
    fact = factorization(N)
    ff = []
    for fn in fact:
        for i in range(fn[1]):
            ff.append(fn[0])
    ans = 10000000000000
    fN = len(ff)
    for wake in range(2**fN):
        wake2 = format(wake, '0'+str(fN)+'b')
        A = 1
        for i in range(fN):
            if wake2[i] == '1':
                 A = A*ff[i]   
        B = N / A
        if A + B - 2 < ans:
            ans = int(A+B-2)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
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())
data=prime_factorize(N)

ans=10**12
for i in range((len(data))//2+1):
  for subset in itertools.permutations(data, i):
    a=1
    for e in subset:
      a*=e
    b=N//a
    ans=min(ans,a+b)
print(ans-2)

Submission status: Time Limit Exceeded

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

while n < N:
    if (N/n).is_integer() == True:
        print(int(N/n + n - 2))
        break
    else:
        n += 1

Submission status: Time Limit Exceeded

Solution code:
#%%

#%%
n = int(input())

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

l = factorize(n)


import itertools
c = list(itertools.product(range(2), repeat=len(l)))
#print(c)

flag = False
k = 10**15
for i in range((len(c)+1)//2):
    a = 1
    b = 1
    for j in range(len(c[i])):
        if c[i][j] == 0:
            a *= l[j]
        else:
            b *= l[j]
    k = min(k, a+b)
    

print(k-2)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
min_steps=a
if a==2:
    print(1)
elif a==3:
    print(2)
else:
    for i in range(2, int(a/2)+1):
            if a%i==0:
                b=i+int(a/i)-2
                if b<min_steps:
                    min_steps=b
    if (min_steps==a):
        min_steps-=1
    print(min_steps)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    N = int(input())
    nmin = 10**12
    if N == 1:
        print(0)
        exit()
    for n in range(1, max(2, N//2)):
        if N % n == 0:
            nmin = min(nmin, n + N//n - 2)

    print(nmin)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

l = []

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

print(min(l))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = N -1

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math


def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1


def main(n):
    if is_prime(n):
        return n - 1
    else:
        sqrt = int(math.sqrt(n))
        for i in range(sqrt, n + 1):
            div, mod = divmod(n, i)
            if mod == 0:
                return i + div - 2


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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

answer_list=[]
for i in range(1, int((N/2))+1):
    if N % i == 0:
        s = N/i
        answer_list.append(s+i)

print(int(min(answer_list)) - 2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
def divisor_list(num):
  ans = []
  for i in range(1, int(num**0.5)+1):
    if num % i == 0:
      ans.append(i)
      if i != num // i:
        ans.append(num//i)
  return ans
d_list = sorted(divisor_list(N))
ans = 10**12
for i in d_list:
  for j in d_list:
    if i*j == N and ans > i+j-2:
      ans = i+j-2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 1000000000001

for i in range(N):
  if N % (i+1) == 0:
    if (N/(i+1)) + (i+1) -2 < ans:
      ans = int((N/(i+1)) + (i+1) -2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def prime_factorization(n):
    factor = []
    f = 2
    while f ** 2 <= n:
        if n % f == 0:
            factor.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        factor.append(n)
    return factor

p = prime_factorization(N)
from itertools import combinations as cb
from functools import reduce
from operator import mul

s = float('inf')
for i in range(1,len(p)+1):
    for j in cb(p, i):
        A = reduce(mul, j)
        B = N//A
        s = min(s, A+B)

print(s-2)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  n=I()

  a=getPrimeList(n)

  # l=[]
  # b=len(bin(1<<len(a)))-3
  # for i in range(1<<len(a)):
  #   l.append(str(bin(i))[2:].zfill(b))
  
  # ans=inf
  # for x in l:
  #   _a=_b=1
  #   for i,y in enumerate(list(x)):
  #     if y=='0':
  #       _a*=a[i]
  #     else:
  #       _b*=a[i]
  #   ans=min(ans,_a+_b-2)

  # return ans

  ans=inf
  b=len(a)
  for i in range(2**b):
    _a=_b=1
    for j in range(b):
      if ((i >> j) & 1):
        _a*=a[j]
      else:
        _b*=a[j]
    ans=min(ans,_a+_b-2)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mx = int(10e6+1)
y=0
mn = int(10e13)
for v in range(1,mx):
    if v<=n and n%v==0:
        y=1
        left = n//v
        mn=min(v-1+left-1,mn)
    if v>n:
        break
if y:
    print(mn)
else:
    print(n-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

divs = []

for i in range(n + 1):
  if i == 0:
    continue
  mod = n % i
  if mod == 0:
    divs.append(i)

center = int(len(divs) / 2)
print(divs[center-1] + divs[center] -2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

last_num = n // 2 + 1
can_division = [i for i in range(1, last_num) if n%i == 0]
can_division.extend([n])

can_division_sorted = can_division[::-1]

sum_num = []
for i in range(len(can_division)):
    sum_num.append((can_division[i]-1) + (can_division_sorted[i]-1))
print(min(sum_num))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

box = []
for i in range(1, N + 1): 
    if N % i == 0:
        box.append(int(N / i)) 

a = box[int(len(box)/2)]
b = int(N / a)

kkk = (a-1) + (b-1)

print(kkk)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=0
n_lis=[]
for i in range(1,(n//2)+1):
  if n%i==0:
    n_lis.append((i-1)+(n//i-1))
n_l=sorted(n_lis)
ans=n_l[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
list=[]
for t in range(1,N+1):
  if N%t==0:
    list+=[(t,int(N/t))]
mini=N+1
for (p,q) in list:
  if p+q<mini:
    mini=p+q
print(mini-2)

Submission status: Time Limit Exceeded

Solution code:
#%%

#%%
n = int(input())

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

l = factorize(n)


import itertools
c = list(itertools.product(range(2), repeat=len(l)))
#print(c)

flag = False
k = 10**15
for i in range(len(c)):
    a = 1
    b = 1
    for j in range(len(c[i])):
        if c[i][j] == 0:
            a *= l[j]
        else:
            b *= l[j]
    k = min(k, a+b)
    

print(k-2)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    N = int(input())
    nmin = 10**12
    if N == 1:
        print(0)
        exit()
    for n in range(1, N):
        r = N % n
        if r == 0:
            if n + N//n - 2 < nmin:
                nmin = n + N//n - 2

    print(nmin)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
min_steps=a
if a==2:
    print(1)
elif a==3:
    print(2)
else:
    for i in range(2, int(a/2)+1):
            if a%i==0:
                b=i+int(a/i)-2
                if b<min_steps:
                    min_steps=b
    print(min_steps)

Submission status: Time Limit Exceeded

Solution code:
#C問題
#考え方：平方根に近いところを探す。
#平方根を切り上げた値からスタート。割り切れた時点で終了。
#TLEになった。原因として考えられるのは何か？ものすごい大きな数の時にうまくいかない？
import math
N = int(input())
sq_N = int(math.sqrt(N))
i = 0
while True:
    if N ==1:
        A = 1
        B = 1
        break;
    elif N% (sq_N+i) ==0:
        A = sq_N+i
        B = int(N/A)
        break;
    else:
        i = i+1
print(A-1+B-1)

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

plist=prime_factorize(N)
ctr=pow(2,len(plist))
minctr=N
#print(plist)
for i in range(ctr):
    a=1
    b=1
    ctr_str=format(i,'0'+str(len(plist))+'b')
    #print(ctr_str)
    for j in range(len(ctr_str) ):
        if ctr_str[j] == '0':
            a=a*plist[j]
        else:
            b=b*plist[j]
    #print(a,b)
    minctr = min(minctr,a+b-2)

print(minctr)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy

# 入力 =stdin.readline().rstrip()
# 分割 = stdin.readline().rstrip().split()

'''
条件に合うものを絞り込む
data = [1, 2, 3]
s = [x for x in data if x % 3 == 0]
'''

'''
文字配列を数値に
l_si = ['-10', '0', '100']

l_si_i = [int(s) for s in l_si]
'''

'''
a = [2, 4, 6, 8]
b = [3, 6, 9]

print(list(set(a) | set(b)))  # 和集合
print(list(set(a) & set(b)))  # 積集合
'''

'''
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
count = 0
while len([x for x in A if x % 2 == 0]) == N:
    A = list(map(lambda y: y / 2, A))
    count += 1
print(count)
'''

'''
.append(要素)
.extend(要素)
.insert(場所,要素)
del 配列名[場所]
-1で末尾で末尾から一つ前
'''
'''
間に空白追加
' '.join(lis)
'''
'''
copy.copy(配列名)
'''
'''
sort()50
sorted(reverse=true)
'''
'''
2分探索
bisect.bisect_left(リスト, 要素)
'''
num = int(stdin.readline().rstrip())
yaku = []
for el in range(1, num + 1):
    if (num % el == 0):
        yaku.append(el)
res = []
if (int(len(yaku)) % 2 == 0):
    res.append(yaku[int(len(yaku) / 2 - 1)])
    res.append(yaku[int((len(yaku)) / 2)])
    print(int(res[0]-1)+int(res[1]-1))
else:
    res.append(yaku[int((len(yaku)) / 2)])
    print(int(res[0]-1)+int(res[0]-1))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
c=0
INF=2000000
x=[0 for _ in range(INF)]
y=[0 for _ in range(INF)]

for i in range(N):
    for j in range(N) :
        if (i+1)*(j+1)==N:
            x[c]=i
            y[c]=j
            c+=1

d=INF
for i in range(c):
    if d>(x[i]+y[i]):
        d=x[i]+y[i]

print(d)

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

def solve():
    n = int(input())
    if is_prime(n):
        print(n-1)
        return
    half = int(math.sqrt(n))
    for i in range(half, n):
        if n % i == 0:
            a = i
            b = n // i
            print(a + b - 2)
            return
    return 

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
i = int(N ** 0.5)
while i != 1:
  if N % i == 0:
    N //= i
    break
    
print(N + i - 2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

factor_a = 0
factor_b = 0
for i in range(int(n ** 0.5), n+1):
	if n % i == 0:
		factor_a = i
		factor_b = n / i
		break

print(int(factor_a - 1 + factor_b - 1))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mini = (10** 12)+1
X=0
Y=0
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
ans = make_divisors(n)
for i in range(len(ans)):
  for j in range(len(ans)):
    if mini>ans[i]-ans[j] and n==ans[i]*ans[j] and ans[i]>=ans[j]:
      mini =ans[i]-ans[j]
      X=ans[i]
      Y=ans[j]
print(X-1+Y-1)

Submission status: Time Limit Exceeded

Solution code:
import math

n=int(input())

minimum=n-1
for i in range(1,n):
    if(n%i==0):
        minimum=min(minimum,(n//i-1)+(i-1))

print(minimum)

Submission status: Time Limit Exceeded

Solution code:
import math

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

Submission status: Time Limit Exceeded

Solution code:
#n,k = map(int,input().split())
#a_L = list(map(int,input().split()))

n = int(input())
ans_L = []
for val in range(1,int(n/2+1)):
    if n % val ==0:
        x = val
        y = n/val
        ans_L.append(int(x+y-2))

#print(ans_L)
print(min(ans_L))

Submission status: Time Limit Exceeded

Solution code:
#C問題
#考え方：平方根に近いところを探す。
#平方根を切り上げた値からスタート。割り切れた時点で終了。
import math
N = int(input())
sq_N = int(math.sqrt(N))
i = 0
while True:
    if N% (sq_N+i) ==0:
        A = sq_N+i
        B = int(N/A)
        break;
    else:
        i = i+1
print(A-1+B-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ls = []
    t = n
    for i in range(2, int(n ** 0.5) + 1):
        while True:
            if t % i == 0:
                ls.append(i)
                t //= i
            else:
                break
    if t != 1:
        ls.append(t)
    mt = 10 ** 20
    for i in range(len(ls)):
        for v in itertools.combinations(ls, i):
            t = 1
            for vv in v:
                t *= vv
            mt = min(mt, (t - 1) + (n // t - 1))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

N = int(input())

# 全部はいらないのでざっくりフィルタ
# lim = int(math.sqrt(N)) + 1
lim = (N // 2 ) + 1

min_count = 99999999999999999999
# 約数列挙してからのほうが早いか？
divisors = make_divisors(N)
for i in divisors :
    for k in divisors :
        if (i*k == N) :
            c = (i-1) + (k-1)
            if (c < min_count ) :
                min_count = c


# for i in range(1,lim+1) :
#     for k in range(1,lim+1) :
#         if (i*k == N) :
#             c = (i-1) + (k-1)
#             if (c < min_count ) :
#                 min_count = c

print(min_count)

Submission status: Time Limit Exceeded

Solution code:
i = int(input())
c = i
l = []
while c != 1:
	if i % c == 0:
		l.append(c)
	c -= 1
ll = []
for x in l:
	ll.append(i//x)
lll = []
for a,b in zip(l,ll):
	cc = a + b - 2
	lll.append(cc)
print(min(lll))

Submission status: Time Limit Exceeded

Solution code:
#%%

#%%
n = int(input())

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

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

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

    return arr

x = factorization(n)
#print(x)

l = []
for i in range(len(x)):
    for j in range(x[i][1]):
        l.append(x[i][0])
#print(l)


import itertools
c = list(itertools.product(range(2), repeat=len(l)))
#print(c)

flag = False
k = 10**15
for i in range(len(c)):
    a = 1
    b = 1
    for j in range(len(c[i])):
        if c[i][j] == 0:
            a *= l[j]
        else:
            b *= l[j]
    k = min(k, a+b)
    

print(k-2)

Submission status: Time Limit Exceeded

Solution code:
#n,k = map(int,input().split())
#a_L = list(map(int,input().split()))

n = int(input())
ans_L = []
for val in range(1,n+1):
    if n % val ==0:
        x = val
        y = n/val
        ans_L.append(int(x+y-2))

#print(ans_L)
print(min(ans_L))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = float("inf")


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


for i in make_divisors(N):
    for j in make_divisors(N):
        if i * j == N:
            x = i - 1
            y = j - 1

            ans = min(ans, (i-1)+(j-1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ans = N-1

def get_steps(a, b):
    return (a-1) + (b-1)


for i in range(1, N//2+1):
    if N % i == 0:
        d = N // i
        ans = min(ans, get_steps(i, d))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
m = int(math.sqrt(n))
while True:
  if n%m==0:
    print(n//m + m - 2)
    exit()
  m += 1

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  n=I()

  a=getPrimeList(n)

  l=[]
  b=len(bin(1<<len(a)))-3
  for i in range(1<<len(a)):
    l.append(str(bin(i))[2:].zfill(b))
  
  ans=inf
  for x in l:
    _a=_b=1
    for i,y in enumerate(list(x)):
      if y=='0':
        _a*=a[i]
      else:
        _b*=a[i]
    ans=min(ans,_a+_b-2)

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n=int(input())
l=[]
i=1
ans=10000000000000
while i<n**(1/2):
    if n%i==0:
        ans=n//i+i-2
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ans = 10**12
for i in range(1,int(N**0.5)+1):
    j = N/i
    if(j == int(j)):
        ans = i+j-2
print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())

import math
ans = []
for i in range(1,int(math.sqrt(n))+1):
  if n % i == 0:
    b = int(n/i)
    ans.append(i+b-2)
print(min(ans))

Submission status: Accepted

Solution code:
n = int(input())

furui = [i for i in range(10**6+2)]

ans = 9999999999999

yakusuu = []

for i in range(1,int(n**0.5)+1+1):
    
    if n%i == 0:
        
        yakusuu.append(i)
        

    
for i in yakusuu:
    
    ans = min(i+n//i,ans)
    # print(i,ans)
    
print(ans-2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
N_ri = round(pow(N, 1/2))

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

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    n = int(input())
    ans=10**12
    tmp=[]
    for a in range(1,10**6+1):
        if n%a==0 and n >=a:
            b=n//a
        elif n <a:
            break
        #a,bの最小値を記憶してくれてる？
        ans=min(ans,a+b-2)
    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    n = int(input())
    ans=10**12
    for a in range(1,10**6+1):
        if n%a==0:
            b=n//a
        ans=min(ans,a+b-2)
    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

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

ans = float("inf")
for i in range(1,int(math.sqrt(n)+1)):
    if n%i == 0:
        if (i-1)+(n//i-1) < ans:
            ans = (i-1)+(n//i-1)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
ans=float("inf")
i=1
while i**2<=N:
  if N%i==0:
    temp=(i-1)+(N//i -1)
    ans=min(ans, temp)
  i+=1
print(ans)

Submission status: Accepted

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

a,b = 1,n
for i in range(1,int(math.sqrt(n)+1)):
    if n%i == 0:
        q = n//i
        if abs(a-b) > abs(q-i):
            a,b = i,q

print((a-1) + (b-1))

Submission status: Accepted

Solution code:
def divisor(n): 
    i = 1
    table = []
    while i*i<=n:
        if n%i==0:
            table.append([i,n//i])
        i+=1
    return table

N = int(input())
m = N

if len(divisor(N))==1:
  print(N-1)

else:
  for i,j in divisor(N):
    m = min(m,i+j)
  print(m-2)

Submission status: Accepted

Solution code:
n = int(input())
x = int(n**(1/2))+1
for i in range(1, x+1):
    if n%i == 0:
        p = i
        q = n//i
print(p+q-2)

Submission status: Accepted

Solution code:
N = int(input())

num = set()
for n in range(2, 10**7):
    if N % n == 0:
        num.add(tuple(sorted([n, N//n])))
    if N == n:
        break
ans = (10**12, 10**12)
if not num:
    print(N - 1)
else:
    for s in num:
        if s[0]+s[1] < ans[0]+ans[1]:
            ans = s
    print(ans[0] + ans[1] - 2)

Submission status: Accepted

Solution code:
from math import sqrt
n=int(input())
ans=float('inf')
for i in range(1,int(sqrt(n))+1):
  if n%i==0:
    res=i+n//i-2
    ans=min(ans,res)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = 10**12
for a in range(1,10**6+1):
    if n%a==0:
        b=n//a
    ans = min(ans,a+b-2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    N = int(input())
    d = make_divisors(N)
    d.reverse()
    ans = float('inf')
    for i in range(N):
        if len(d) == 1:
            a = d.pop()
            ans = min(ans, 2*(a-1))
            break
        if len(d) == 0:
            break
        a = d.pop()-1
        b = d.pop()-1
        ans = min(ans, a+b)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
# 99分解して、マンハッタン距離を求める
# ただし、iとjが近い方が距離が短くなる

cand = 1
n = 1
while n * n <= N:
  if N % n == 0:
    cand = n
  n += 1

print(cand - 1 + N // cand - 1)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

result = [10**13]
cnt = []
for i in range(1,int(math.sqrt(N))+1) :
    if N % i == 0 :
        buf = min(result[-1],i+(N//i))
        result.append(buf)
        if result[-1] != result[-2] :
            cnt.append([i,N//i])


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

Submission status: Accepted

Solution code:
N = int(input())
ans = 10 ** 12 + 1
for a in range(1, int(N ** 0.5 + 2)):
    if N % a == 0:
        a_b = a + (N // a) - 2
    if ans > a_b:
        ans = a_b

print(int(ans))

Submission status: Accepted

Solution code:
import math

n = int(input())
List = []
n_sqrt = int(math.sqrt(n))

for i in range(1,n_sqrt+1):
    if n % i == 0:
        number = i + (n // i) -2
        List.append(number)
        
print(min(List))