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())
list = []
for i in range(1,N+1):
    if N%i==0:
        list.append(i)
listnum = len(list)
list2 = []
for j in range(listnum):
    S = list[j]+list[listnum-1-j]-2
    list2.append(S)
print(min(list2))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

for x in range(1, 10**6+1):
    if x**2 >= n:
        y = x
        break

i, j = y, y
while True:
    if i*j == n:
        ans = i + j - 2
        break
    elif i*j > n:
        i -= 1
    elif i*j < n:
        j += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ln = []
for k in range(1,n+1):
    if n % k == 0:
        ln.append(k)
if not n**0.5 % 1 == 0:
    i = ln[len(ln) // 2 - 1]
    j = ln[len(ln) // 2]
    ans = i + j -2
else:
    ans = int(2*n**0.5)-2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=n+1
i=1
while i*i<=n:
    if n%i==0 and ans > n%i+n/i:
        ans = n%i + n/i
print(ans-2)

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

N=int(input())
Flist=factorization(N)
F_list=[]
for i in Flist:
    F_list+=[i[0]]*i[1]
F_list.sort()
data=[[1,1] for i in range(2**len(F_list))]
for i in range(2**len(F_list)):
    for m,s in enumerate("0"*(len(F_list)-len(bin(i)[2:]))+bin(i)[2:]):
        if int(s):data[i][0]*=F_list[m]
        else     :data[i][1]*=F_list[m]
data2=data[[i[0]-i[1] for i in data].index(min([abs(i[0]-i[1]) for i in data]))]
print(data2[0]+data2[1]-2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import copy
N = int(input())

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)
if len(a) == 1:
  print(a[0] - 1)
  sys.exit()

kyori = []
for i in range(1, len(a)):
  j = list(itertools.combinations(a, i))
  k = list(dict.fromkeys(j))
  for l in k:
    diff = copy.deepcopy(a)
    for m in l:
      if m in diff:
        diff.remove(m)
    A = 1
    for i_l in l:
      A *= i_l
    B = 1
    for i_diff in diff:
      B *= i_diff
    kyori.append(A + B - 2)

print(min(kyori))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
factor = []
tmp = n
for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
if tmp != 1:
    factor.append(tmp)
w = len(factor)
if w == 0:
    factor.append(n)
    w = 1
if w == 1:
    print(n - 1)
else:
    ans = 1000000000000
    for i in range(1, 2 ** w // 2):
        f2 = [1, 1]
        for j in range(w):
            f2[i & (2 ** j) == 0] *= factor[j]
        ans = min(ans, sum(f2) - 2)
        if ans < n ** 0.5 * 2:
            break
    print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
# a, b, x = map(lambda i: int(i), input().split(' '))

def main():
    # hen1 = a / 2
    # hen2 = b - (x / (a * a))
    # print(math.degrees(math.atan(hen2 / hen1)))
    primes = prime_factorize(N)
    if len(primes) == 1:
        print(primes[0] - 1)
        return
    elif len(primes) == 2:
        print(primes[0] + primes[1] - 2)
        return

    min = -1
    for i in range(1, len(primes) + 1):
        for v in itertools.combinations(primes, i):
            a = reduce(mul, list(v))
            b = N // a
            if min == -1 or min > (a + b - 2):
                min = a + b - 2
    print(min)

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

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import random

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1
        if y != n - 1 and t & 1 == 0:
            return False
    return True

def sqrt2(n):
    if is_prime(n):
        return (n, 1)
    start = round(math.sqrt(n))
    i = 0
    while True:
        if n % (start + i) == 0:
            return (start + i), n // (start + i)
        i += 1
    return (0, 0)

N = int(input())
a, b = sqrt2(N)
print(a + b - 2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
from functools import reduce

N = int(input())
distance = []
C = []

def prime_f(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_f(N)

if len(A) == 1:
  print(N - 1)
else:
  for i in range(1,len(A)):
    C = list(set(itertools.combinations(A,i)))
    for j in range(0,len(C)):
      totalC = reduce(lambda x,y:x*y,C[j])
      div = int(N / totalC)
      distance.append(div + totalC)

  print(min(distance) - 2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


def devide2(x):
    ar = []
    for i in range(1, int(x)):
        if x % i == 0:
            ar.append([i, x // i])
    return ar


kumi = devide2(n)

ans = 10 ** 12 + 1000
for i in range(len(kumi)):
    ans = min(ans, sum(kumi[i]))

print(ans - 2)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
from functools import reduce

N = int(input())

def prime_f(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_f(N)

F = []
L = []

distance = []

C = []

if len(A) == 1:
  print(N - 1)
else:
  for i in range(1,len(A)):
    C = list(itertools.combinations(A,i))
    for j in range(0,len(C)):
      totalC = reduce(lambda x,y:x*y,C[j])
      div = int(N / totalC)
      distance.append(div + totalC)

  print(min(distance) - 2)

Submission status: Time Limit Exceeded

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


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

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

    return N - 1


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

    return nearest


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


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


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


main()

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
L = []

for i in range(1,1000000000001):
  for j in range(1,1000000000001):
    if i * j == N: 
      L.append(i + j - 2)
print(min(L))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

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

a = []
b = []

if len(s_)//2 == 0:
    idx = 1
else:
    idx = len(s_)//2
    
for i in range(idx):
    c = list(itertools.combinations(s_,i+1))
    for j in range(len(c)):
        d = list(c[j])
        p = np.prod(d)
        a.append(p)
        b.append(n/p)
        
e = []
for i in range(len(a)):
    e.append(a[i]+b[i]-2)
print(int(min(e)))

Submission status: Time Limit Exceeded

Solution code:
# C - Walk on Multiplication Table
n = (int)(input())

flg = False

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

print(minimum)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from collections import deque


def p_f(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


hoge = p_f(N)
DP = deque()
DP.append(1)

if len(hoge) == 1:
    print(hoge[0]-1)
else:
    Min = 10**12

    for i in range(len(hoge)):
        for j in range(len(DP)):
            x = DP[j]*hoge[i]
            DP.append(x)
            if (x + (N // x) - 2) < Min:
                Min = (x + (N // x) - 2)

    print(Min)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
def factorize(n):
    b = 2
    fct = []
    end = int(n ** (0.5)) + 2
    for b in range(2, end):
      while n % b == 0:
        n //= b
        fct.append(b)
      if n == 1:
        break
    if n > 1:
      fct.append(n)
    return fct
 
fact = factorize(n)
dif = []
from itertools import combinations as com
for i in range((len(fact) + 1) // 2 + 1):
  for cands in com(fact, i):
    ans = 1
    for cand in cands:
      ans *= cand
    dif.append(n//ans + ans - 2)
print(min(dif))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
factor = []
tmp = n
for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
if tmp != 1:
    factor.append(tmp)
w = len(factor)
if w == 0:
    factor.append(n)
    w = 1
if w == 1:
    print(n - 1)
else:
    ans = 1000000000000
    for i in range(1, 2 ** w // 2):
        f2 = [1, 1]
        for j in range(w):
            f2[i & (2 ** j) == 0] *= factor[j]
        ans = min(ans, sum(f2) - 2)
        if ans < n ** 0.5 * 1.5:
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

sum = 0
tmp1 = 0
tmp2 = 0
for i in range(1, N + 1):
    if N % i == 0:
        div = int(N / i)

        if i + div > sum and i != 1:
            print('{}'.format(tmp1 + tmp2 - 2))
            exit()
        else:
            sum = i + div
            tmp1 = i
            tmp2 = div

print('{}'.format(tmp1 + tmp2 - 2))

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


a=int(input())
i=2
j=1
flag=0
x=0
y=0
min=a**0.5
intmin=int(min)
if not is_prime(a):

    for i in range(intmin,a):
        if a%i == 0:
            if i!=a:
                print(int(i-2+(a/i)))
            else:
                print(a-1)
            break
else:
    print(a-1)



# try:
#     for i in range(2,a//2):
#         mod=a%i
#         if mod==0:
#             if min > (a/i) + i -2:
#                 min = (a/i) + i -2
#     print(min)
# except ZeroDivisionError:
#     print("ZeroDivisionError!!")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


def p_f(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


hoge = p_f(N)

DP = [1]

if len(hoge) == 1:
    print(hoge[0]-1)
else:
    Min = 10**12

    for i in range(len(hoge)):
        for j in range(len(DP)):
            x = DP[j]*hoge[i]
            DP.append(x)
            if (x + (N // x) - 2) < Min:
                Min = (x + (N // x) - 2)

    print(Min)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
lst = []
i = int(1)
j = int(1)
imax = 10 ** 12
jmax = 10 ** 12


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


if(is_prime(n)):
    print(n-1)
else:
    while(i <= imax):
        while(j <= jmax):
            if i*j == n:
                lst.append(i+j-2)
                imax = j
                jmax = j
                i += 1
                j = int(1)
                break
            elif(j == jmax):
                i += 1
                j = int(1)
                break
            else:
                j += 1
        else:
            i += 1
    else:
        print(min(lst))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

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

ans=[]
for num,cnt in factorization(n):
  for _ in range(cnt):
    ans.append(num)
out=float('inf')
tmp=[]
for i in range(2**len(ans)//2):
  tmp1,tmp2=1,1
  for j in range(len(ans)):
    if i>>j&1:
      tmp1*=ans[j]
    else:
      tmp2*=ans[j]
  out=min(out,tmp1-1+tmp2-1)
print(out)

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
m = ((len(L)+1)//2) + 1
for i in range(1,len(L)+1):
    if i<=m:
        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:
import itertools

a = 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

arr0 = factorization(a) 


arr1 = [arr0[i][0] for i in range(len(arr0))]
arr2 = [arr0[i][1] for i in range(len(arr0))]

ab = []
for i in range(len(arr1)):
    for j in range(arr2[i]):
        ab.append(arr1[i])

abc = []
for i in range(1,sum(arr2)+1):
    abc.extend(list(itertools.combinations(ab, i)))

abcd = []

for i in range(len(abc)):
    g = 1
    for j in range(len(abc[i])):
        g *= abc[i][j]
    
    abcd.append(g)


abcde = [[i,a//i] for i in abcd]
abcdef = [sum(abcde[i]) for i in range(len(abcde))]
print(min(abcdef)-2)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())

i, j = 1, 1
footsteps = []
while i * j != N:
    footsteps.append((i, j))
    left = (i - 1) * j
    up = i * (j - 1)
    right = (i + 1) * j
    down = i * (j + 1)
    distances = {
            (i - 1, j): abs(N - left),
            (i, j - 1): abs(N - up),
            (i + 1, j): abs(N - right),
            (i, j + 1): abs(N - down),
            }
    items = distances.items()
    items = filter(lambda (k, v): k not in footsteps, items)
    i, j = min(items, key=lambda (k, v): v)[0]
print i - 1 + j - 1

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

n=int(input())
F = [1]
for i, j in factorization(n):
    for _ in range(j):
        F.append(i)
import itertools
ans = 9999999999999
for flags in itertools.product([0,1], repeat=len(F)):
    a = 1
    b = 1
    for i in range(len(F)):
        if flags[i]:
            a *= F[i]
        else:
            b *= F[i]
    tmp = (a-1) + (b-1)
    if tmp < ans:
        ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

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

ans=[]
for num,cnt in factorization(n):
  for _ in range(cnt):
    ans.append(num)
out=float('inf')
tmp=[]
for i in range(2**len(ans)):
  tmp1,tmp2=1,1
  for j in range(len(ans)):
    if i>>j&1:
      tmp1*=ans[j]
    else:
      tmp2*=ans[j]
  out=min(out,tmp1-1+tmp2-1)
print(out)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


def p_f(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


hoge = p_f(N)

DP = [1]

if len(hoge) == 1:
    print(hoge[0]-1)
else:
    Min = 10**12

    for i in range(len(hoge)):
        for j in range(len(DP)):
            
            DP.append(DP[j]*hoge[i])

    for i in range(len(DP)):
        if (DP[i] + (N//DP[i]) - 2) < Min:
            Min = (DP[i] + (N//DP[i]) - 2)
            
    print(Min)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
factor = []
tmp = n
for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
if tmp != 1:
    factor.append(tmp)
w = len(factor)
if w == 0:
    factor.append(n)
    w = 1
if w == 1:
    print(n - 1)
else:
    ans = 1000000000000
    for i in range(1, 2 ** w // 2):
        f2 = [1, 1]
        for j in range(w):
            f2[i & (2 ** j) == 0] *= factor[j]
        ans = min(ans, sum(f2) - 2)
        if ans < n ** 0.5 * 1.1:
            break
    print(ans)

Submission status: Time Limit Exceeded

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

print(m-2)

Submission status: Time Limit Exceeded

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

def isPrime(n) : 
  
    # Corner cases 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
  
    # This is checked so that we can skip  
    # middle five numbers in below loop 
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True




#if isPrime(N):
#  print(N - 1)
#else:
x = math.floor(N**(0.5))
for i in range(x,N+1):
  a = N/i
  if (a%1 == 0):
    print(int(a) + i -2)
    break
else:
  print(N-1)

Submission status: Time Limit Exceeded

Solution code:
# min x+y s.t. x*y=N
import math
import random

def is_prime(n):
    if n == 1: return False
    if n == 2: return True

    for k in range(100):
        a = random.randint(2, n - 1)

        if gcd(n, a) != 1:
            return False

        if pow(a, n - 1, n) != 1:
            return False

    return True

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

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

  print(i + j - 2)

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

l = make_divisors(n)
ans = n-1
for i in range(0, len(l)):
  for j in range(0, len(l)):
    a = l[i]
    b = l[j]
    if a * b == n:
      ans = min(ans, (a+b-2))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
factor = []
tmp = n
for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
if tmp != 1:
    factor.append(tmp)
w = len(factor)
if w == 0:
    factor.append(n)
    w = 1
if w == 1:
    print(n - 1)
else:
    ans = 1000000000000
    for i in range(1, 2 ** w // 2):
        f2 = [1, 1]
        for j in range(w):
            f2[i & (2 ** j) == 0] *= factor[j]
        ans = min(ans, sum(f2) - 2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
result = 0
for num in range(1, N+1, 1):
    if N % num == 0:
        a = N // num
        tmp = 0
        if a + num - 2 > 0:
            tmp = a + num - 2

        if result == 0:
            result = tmp
        elif result > tmp:
            result = tmp


print(result)

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 factorization2(n):
    arr = []
    arr2=[]
    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
                arr2.append(i)
            arr.append([i, cnt])

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

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

    return arr2

N=int(input())

fct=factorization(N)


ary=[]
for sf in fct:
    tmp=[sf[0]]*sf[1]
    ary.extend(tmp)

import numpy as np

#def search(i):

#search()

from itertools import chain,combinations
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))



res=10**13
for sp in powerset(ary):
    if len(sp)!=0:
        tmp=np.product(sp)
    else:
        tmp=1
    b=N/tmp
    res=min(tmp+b-2,res)

print(int(res))

Submission status: Time Limit Exceeded

Solution code:
def dfs(n):
    table =[]
    i = 2
    while n >= i**2:
    # nのその数自身を除いた素因数は√n以下であることから。
        while n % i == 0:
            table.append(i)
            n /= i
        i += 1
    if n > 1:
        table.append(int(n))
# 最後に残った、最大の素因数をリストに入れる。
    return table

N = int(input())
f_list = dfs(N)
if len(f_list) == 1:
  print(f_list[0] - 1)
  exit()
elif len(f_list) == 2:
  s = 0
  for f in f_list:
    s += f
  print(s - 2)
  exit()
ans = float('inf')
for x in range(10**12):
  if x + 1 > N:
    break
  for y in range(10**12):
    if (x + 1) * (y + 1) > N:
      break
    if (x + 1) * (y + 1) == N:
      ans = min((x + y), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

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

ans=[]
for num,cnt in factorization(n):
  for _ in range(cnt):
    ans.append(num)
out=float('inf')
for i in range(2**len(ans)):
  tmp1,tmp2=1,1
  for j in range(len(ans)):
    if i>>j&1:
      tmp1*=ans[j]
    else:
      tmp2*=ans[j]
  out=min(out,tmp1-1+tmp2-1)
print(out)

Submission status: Time Limit Exceeded

Solution code:
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())
m=N+1
for i in range(1,N//2+1):
    for j in range(2,N//2+1):
        if i*j==N:
            m=min(m,(i+j))
print(m-2)

Submission status: Time Limit Exceeded

Solution code:
import collections
import copy

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

x = int(input())
master_c = prime_factorize(x)
if len(master_c) == 1:
    print(x-1)
else:
    min_num = x-1
    for i in range(2,int(x/2)):
        if x % i == 0:
            num = int(i+(x/i)-2)
            if num < min_num:
                min_num = num
    print(min_num)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = []
i = int(1)
j = int(1)
imax = 10 ** 12
jmax = 10 ** 12

while(i <= imax):
    while(j <= jmax):
        if i*j == n:
            lst.append(i+j-2)
            imax = j
            jmax = j
            i += 1
            j = int(1)
            break
        elif(j == jmax):
            i += 1
            j = int(1)
            break
        else:
            j += 1
    else:
        i += 1
else:
    print(min(lst))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
a = input()
a = int(a)

n = a

for i in range(1, a):
    if a % i == 0:
        b = int(a / i)
        n1 = (i - 1) + (b - 1)
        n = min(n , n1)

print(n)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

tmp = [(i,N//i) for i in range(1,1000000000000) if N % i == 0]

res = 100000000000
for i, x in tmp:
    Min =  (i-1) + (x-1)
    if res > Min:
        res = Min

print(res)

Submission status: Time Limit Exceeded

Solution code:
a = input()
a = int(a)

n = a

for i in range(1, a + 1):
    if a % i == 0:
        b = int(a / i)
        n1 = (i - 1) + (b - 1)
        n = min(n , n1)

print(n)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
factor = []
tmp = n
for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
if tmp != 1:
    factor.append(tmp)
w = len(factor)
if w == 0:
    factor.append(n)
    w = 1
if w == 1:
    print(n - 1)
else:
    ans = 1000000000000
    for i in range(1, 2 ** w):
        f2 = [1, 1]
        for j in range(w):
            f2[i & (2 ** j) == 0] *= factor[j]
        ans = min(ans, sum(f2) - 2)
    print(ans)