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: Wrong Answer

Solution code:
import math

N = int(input())

n = math.ceil(math.sqrt(N))
lens = [N-1]
for a in range(2, n):
  if N % a == 0:
    lens.append(a+N//a-2)

print(min(lens))

Submission status: Wrong Answer

Solution code:
import math
a = int(input())
x = 0
ans = 1000000000000
for i in range(1,int(math.sqrt(a))):
	if a % i == 0:
		x = int(a / i)
		if ans > ((x - 1) + (i - 1)):
			ans = (x - 1) + (i - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
MIN = 1000000000000
x = 0
for i in range(1,int(math.sqrt(N))):
    if N % i == 0:
        x = int(N / i)
        if MIN > (i + x - 2):
            MIN = i + x - 2

print(int(MIN))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
MIN = 1000000000000
x = 0
for i in range(1,int(math.sqrt(N))):
    if N % i == 0:
        x = int(N / i);
        if MIN > i + x - 2:
            MIN = i + x - 2

print(int(MIN))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
MIN = 1000000000000
for i in range(1,int(math.sqrt(N))):
    if N % i == 0:
        x = N / i;
        if MIN > i + x - 2:
            MIN = i + x - 2

print(int(MIN))

Submission status: Wrong Answer

Solution code:
N = int(input())
MIN = 1000000000000
for i in range(1,int(N / 3)):
    if(N % i == 0):
        if MIN > ((i - 1) + ((N / i) - 1)):
            MIN = ((i - 1) + ((N / i) - 1))

print(int(MIN))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

import math

N = int(input())

res = 10**12+1

if N==1:
    print(0)
else:
    for a in range(1, int(math.sqrt(N))):
        if (N%a)==0:
            b = int(N/a)
            if res>a+b-2:
                res = a+b-2
    
    if res == 10**12+1:
        print(N-1)
    else:
        print(res)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

res = 10**12

if N==1:
    print(0)
else:
    for a in range(1, int(math.sqrt(N))):
        if (N%a)==0:
            b = int(N/a)
            if res>a+b-2:
                res = a+b-2
    
    print(res)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

res = float('inf')
for a in range(1, int(math.sqrt(N))):
    if (N%a)==0:
        b = int(N/a)
        if res>a+b-2:
            res = a+b-2

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())

# ans = 0
div = 1

while n/div > div:
    if n % div == 0:
        # print('a')
        ans = (div-1) + int((n/div-1))
    div += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#ABC144_C
#素因数分解して、N＝なるべく差の小さい2つの因数の積、と考える
import math

init_N=int(input())
N=init_N
ans_list=[]
A=1
B=1

for i in range(2,int(math.sqrt(init_N))+1):
    while 1:  
        if N%i==0:
            ans_list.append(i)
            N=N//i
        else:
            break
if N==1:
    pass
else:
    ans_list.append(N)

if len(ans_list)==1:
    print(str(init_N-1))
else:
    while len(ans_list)>0:
        A=A*ans_list.pop(0)
        #print(A)
        if len(ans_list)!=0:
            B=B*ans_list.pop(0)
            #print(B)
    print(str(A+B-2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
num = int(input())
list = []
min = 0
for i in range(1,num+1):
    p = num/i
    if p.is_integer() == True:
        if list.count(i) == 0 and list.count(int(p)) == 0:
            list.append(i)
            list.append(int(p))
    else:
        break

l = len(list)
list.sort()
if l%2 == 1:
    min = list[int((l/2))]*2-2
else:
    min = list[int(l/2)-1]+list[int(l/2)]-2
print(min)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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


# リストを2分割する
n_insu_list = prime_factorize(n)
bunkai_list = []
# for i in range(1, len(n_insu_list)):
#     bunkai_list.append((np.prod(n_insu_list[:i]), np.prod(n_insu_list[i:])))  # ここが間違っている。
# あらゆる並べ方に対して、この部屋分け的発想を試す必要がある
# n_insu_listを並べ替えたやつ
n_insu_list_list = list(set(list(itertools.permutations(n_insu_list))))
for nlist in n_insu_list_list:
    for i in range(1, len(nlist)):
        bunkai_list.append((np.prod(n_insu_list[:i]), np.prod(n_insu_list[i:])))
bunkai_list = list(set(bunkai_list))
bunkai_list.append((1, n))

# bunkai_listのうち、tupleの和が最小であるものを選び、そのindexを取得する。そのindexのtupleを取得し、そこまでの移動回数を調べる
bunkai_list_sum = [sum(x) for x in bunkai_list]

min_tuple = bunkai_list[bunkai_list_sum.index(min(bunkai_list_sum))]

print(sum(min_tuple) - 2)

Submission status: Wrong Answer

Solution code:
# abc144 C
# 素因数分解してみる（これは後でちゃんと理解しておく！！！）
import numpy as np

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


# リストを2分割する
n_insu_list = prime_factorize(n)
bunkai_list = []
for i in range(1, len(n_insu_list)):
    bunkai_list.append((np.prod(n_insu_list[:i]), np.prod(n_insu_list[i:]) ))
bunkai_list.append((1, n))

# bunkai_listのうち、tupleの和が最小であるものを選び、そのindexを取得する。そのindexのtupleを取得し、そこまでの移動回数を調べる
bunkai_list_sum = [sum(x) for x in bunkai_list]

min_tuple = bunkai_list[bunkai_list_sum.index(min(bunkai_list_sum))]

print(sum(min_tuple)-2)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
a = 1
b = N
nn = math.sqrt(N)
n = math.ceil(nn)

for i in range(2, n):
    if N % i == 0:
        j = N // i    
        if (i + j) < (a + b):
            a = i
            b = j

print(a + b -2)

Submission status: Wrong Answer

Solution code:
n=int(input())
i,j=1,1
for nsum in range(2,n+2):
  for i1 in range(1,i+1):
    j=nsum-i1
    if i1*j==n:
      print(i1+j-2)
      exit(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
i,j=1,1
for nsum in range(2,n+2):
  for i1 in range(1,i+1):
    j1=nsum-i1
    if i1*j1==n:
      print(i+j-2)
      exit(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = []

for x in range(1, 10 ** 6):
  if n % x == 0:
    y = n/x
    li.append(x+y-2)  
     
result = min(li) 
print(int(result))

Submission status: Wrong Answer

Solution code:
#coding: utf-8
import math
import heapq

MOD = 10**9+7

N = int(input())
r = math.ceil(math.sqrt(N))

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

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

import sys

import math
from heapq import heappop,heappush
import heapq

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

res=fac(N)

if N==1:
    print(0)
    sys.exit()

if len(res) == 1: # prime
    print(N-1)
    sys.exit()

heapq.heapify(res)

while(len(res) > 2):
    min1=heapq.heappop(res)
    min2=heapq.heappop(res)
    heapq.heappush(res,min1*min2)

min1=heapq.heappop(res)
min2=heapq.heappop(res)

print(min1+min2-2)

Submission status: Wrong Answer

Solution code:
#ABC144: C - Walk on Multiplication Table

N = int(input())

move = 1000000

for i in range(2,1000001):
    if N % i == 0:
        n = N / i
        for j in range(2,1000001):
            if n / j == 1:
                if i + j < move:
                    move = i + j

print(move - 2)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
ans = N

for x in range(1, int(math.sqrt(N))):
    if N % x == 0:
        if ans > x + int(N / x) - 2:
            ans = x + int(N / x) - 2
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
ans = N
x = 1
y = 1

while x < math.sqrt(N):
    y = 1
    while y < N:
        if x * y == N:
            if ans > x + y - 2:
                ans = x + y - 2
        y += 1
    x += 1

print(ans)

Submission status: Wrong Answer

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

def main():
    Min = 2000000000000
    divisors = make_divisors(int(input()))
    if len(divisors)%2==1:
        divisors.append(divisors[len(divisors)-1])
    print(divisors)
    for i in range(0,len(divisors)-1,2):
        Min = min(divisors[i]+divisors[i+1],Min)
    print(Min-2)

main()

Submission status: Wrong Answer

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

Min = 2000000000000
divisors = make_divisors(int(input()))
for i in range(0,len(divisors)-1,2):
    Min = min(divisors[i]+divisors[i+1],Min)
print(Min-2)

Submission status: Wrong Answer

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

Min = 2000000000000
divisors = make_divisors(int(input()))
for i in range(len(divisors)-1):
    Min = min(divisors[i]+divisors[i+1],Min)
print(Min-2)

Submission status: Wrong Answer

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
 
i = 1
j = 1
for fact in sorted(factorization(N), reverse=True):
    num_fact = fact[0]
    times_fact = fact[1]
    for k in range(times_fact):
        if i < j:
            i *= num_fact
        else:
            j *= num_fact
print(i + j - 2)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':

	n = int(input())
	m = int(n//2)

	end = n - 1
	for x in range(2,int(n**0.5)+1):
		if n % x == 0:
			y = n // x
			end = min(n+m-2,end)

	print(end)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 10**20
a = n ** 0.5
a = int(a)
for i in range(a):
  if i ==0:
    continue
  if n % i != 0:
    continue
  j = n/i
  j = int(j)
  ans = min(ans, i+j-2)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

res = 10 ** 12

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

print(res)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

print(int(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 10**20
a = n ** 0.5
a = int(a)
for i in range(a):
  if i ==0:
    continue
  if n % i != 0:
    continue
  j = n//i
  j = int(j)
  ans = min(ans, i+j-2)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if n==2:
    print(0)
    sys.exit()

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

print(int(min(list)))

Submission status: Wrong Answer

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

i = 1
j = 1
for fact in factorization(N):
    num_fact = fact[0]
    times_fact = fact[1]
    for k in range(times_fact):
        if i < j:
            i *= num_fact
        else:
            j *= num_fact
print(i + j - 2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

# ユークリッドの互除法による最大公約数の算出
def getGCDs(x, y):
    if( x == 0 or y == 0 ):
        return 0
    elif( x > y ):
        divdend,divsor = x,y
    else:
        divdend,divsor = y,x
        
    while(1):
        #quo = divdend / divsor # 商
        rem = divdend % divsor # 余り
        if( rem == 0 ):
            return divsor
        else:
            divdend,divsor = divsor,rem

# 線形合同法による擬似乱数列の生成
def getLCDs(Xn):
    A = 5
    B = 3
    M = 1024
    
    Xn1 = (A * Xn + B) % M
    
    return Xn1

# ポラード・ロー素因数分解
def getPrimefact(n):
    x = 2
    y = 2
    d = 1
    
    while( d == 1 ):
        x = getLCDs( x )
        y = getLCDs( getLCDs( y ) )
        d = getGCDs( abs(x-y), n )

    if( d == n ):
        return False,0
    else:
        return True,d

def getPrimefactLists(n):
    lists = []
    in_n = n
    success = True
    
    if( n == 0 or abs(n) == 1 ):
        lists.append( n )
        return lists
    
    while( success == True ):
        success, result = getPrimefact( in_n )
        if( success == True ):
            if( abs(result) <= 1 ):
                lists.append( in_n )
                break
            else:
                lists.append( result )
            in_n = int( in_n / result )
        else:
            lists.append( in_n )
            break
    
    return lists

# バブルソート
def sortLists(lists):
    if( len(lists) >= 2 ):
        high_to_low = False
        for i in range( 0, len(lists)-1 ):
            for j in range( 0, len(lists)-1 ):
                if( lists[j] > lists[j+1] ):
                    tmp = lists[j+1]
                    lists[j+1] = lists[j]
                    lists[j] = tmp

def getDist(lists):
    dist_i = 1
    dist_j = 0
    
    while(1):
        if( len(lists) <= 0 ):
            break
        else:
            prime_fact = lists.pop(0)
            if( len(lists) <= 0 ):
                dist_j = prime_fact
            else:
                dist_i = dist_i * prime_fact

    result = (dist_i-1) + (dist_j-1)
    return result

# 入力の取得
N = input()
N = int(N)

# 素因数分解実行
result = getPrimefactLists( N )
#result = getPrimefactLists( 745685411 )
#print( result )

# 素数リストのソート(昇順)
sortLists( result )
#print( result )

# 結果出力
dist = getDist( result )
print( dist )

Submission status: Wrong Answer

Solution code:
N=int(input())
 
if N==0:
	print("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
  
total=sorted(make_divisors(N))
a=round(len(total)/2)
print(total[a-1]-1+total[a]-1)

Submission status: Wrong Answer

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)
	return divisors
  
total=sorted(make_divisors(N))
a=round(len(total)/2)
print(total[a-1]-1+total[a]-1)

Submission status: Wrong Answer

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)
	return divisors
 
total=sorted(make_divisors(N))
a=round(len(total)/2)

print(total[a-1]-1+total[a]-1)

Submission status: Wrong Answer

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)
	return divisors
 
total=sorted(make_divisors(N))
print(total[1]-1+total[len(total)-2]-1)

Submission status: Wrong Answer

Solution code:
n = int(input())

for i in range(1, int(n**(1/2))+2 , 1):
    if n%i == 0:
        j = n//i
i = n//j

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

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

route_N = math.sqrt(N)

# a+b-2 minimum
# a*b = N 

ans = 10e+12

for a in range(1,int(route_N)+1):
    if N%a ==0:
        ans = min(ans,a+(N/a)-2)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

Ans = 10**12

for i in range(1,round(N**(0.5))):
    if N % i == 0:
        ans = i + N / i - 2
    Ans = min(Ans, ans)
    
print(int(Ans))

Submission status: Wrong Answer

Solution code:
# 整数の入力
n = int(input())

flag = False

for i in range(1,1000000):
    for j in range(1,1000000):
        if i*j == n:
            I=i
            J=j
            break
    else:
        continue
    break

print((I + J)-2)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = defaultdict(int)
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

N = int(input())
factors = prime_factorization(N)
a, b = 1, 1
count = [0]*2
for p, num in factors.items():
    temp = num // 2
    if count[0] > count[1]:
        a *= p**(temp)
        b *= p**(num - temp)
        count[0] += temp
        count[1] += num - temp
    else:
        a *= p**(num - temp)
        b *= p**(temp)
        count[0] += num - temp
        count[1] += temp
print(a+b-2)

Submission status: Wrong Answer

Solution code:
n = int(input())

div = 2
l = [1]
while True:

    if n % div == 0:
        l.append(div)
        n = n // div
        continue

    div += 1

    if n == 1:
        break

    if n**0.5 < div:
        l.append(n)
        break

l.sort(reverse=True)
x = 1
y = 1
for i in l:
    if x<=y:
        x *= i
    else:
        y *= i

print(x - 1 + y - 1)

Submission status: Wrong Answer

Solution code:
from functools import reduce
n = int(input())

div = 2
l = [1]
while True:

    if n % div == 0:
        l.append(div)
        n = n // div
        continue

    div += 1

    if n == 1:
        break

    if n**0.5 < div:
        l.append(n)
        break

x = l[::2]
y = l[1::2]

x = reduce(lambda a,b:a*b,x)
y = reduce(lambda a,b:a*b,y)

print(x - 1 + y - 1)

Submission status: Wrong Answer

Solution code:
from functools import reduce
n = int(input())


div = 2
l = [1]
while True:

    if n % div == 0:
        l.append(div)
        n = n // div
        continue

    div += 1

    if n**0.5 < div:
        l.append(n)
        break


x = l[::2]
y = l[1::2]

x = reduce(lambda a,b:a*b,x)
y = reduce(lambda a,b:a*b,y)

print(x - 1 + y - 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

list=prime_factorize(n)
num = []
if len(list)!= 0:
    for i in range(len(list)):
        a1,a2 = 1,1

        for j in range(i):
            a1 *= list[j]
        for k in range(i,len(list)):
            a2*=list[k]
        
        num.append(a1+a2)
    print(min(num)-2)

else:
    print(0)

Submission status: Wrong Answer

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

list=prime_factorize(n)
num = []
for i in range(len(list)):
    a1,a2 = 1,1

    for j in range(i):
        a1 *= list[j]
    for k in range(i,len(list)):
        a2*=list[k]
    
    num.append(a1+a2)
print(min(num)-2)

Submission status: Wrong Answer

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

list=prime_factorize(n)
num = []
for i in range(len(list)):
    a1,a2 = 1,1

    for j in range(i):
        a1 *= list[j]
    print("a1",a1)
    for k in range(i,len(list)):
        a2*=list[k]
    print("a2",a2)
    
    num.append(a1+a2)
print(min(num)-2)

Submission status: Wrong Answer

Solution code:
import math
int_n = int(input())
i = (math.sqrt(int_n))
i = math.floor(i)
while i > 1:
    if int_n % i == 0:
        j = int_n/i
        print(math.floor((i - 1) + (j - 1)))
        break
    i = i - 1

Submission status: Wrong Answer

Solution code:
import math
int_n = int(input())
i = (math.sqrt(int_n))
i = math.floor(i)
while i >= 1:
    if int_n % i == 0:
        j = int_n/i
        print((i - 1) + (j -1))
        break
    i = i - 1

Submission status: Wrong Answer

Solution code:
import math
int_n = int(input())
i = (math.sqrt(int_n))
math.floor(i)
while i >= 1:
    if int_n % i == 0:
        j = int_n/i
        print((i - 1) + (j -1))
        break
    i = i - 1

Submission status: Wrong Answer

Solution code:
import math
int_n = int(input())
i = (math.sqrt(int_n))
i = math.floor(i)
while i > 1:
    if int_n % i == 0:
        j = int_n/i
        print((i - 1) + (j -1))
        break
    i = i - 1

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N = int(input())
ans = 10^12
for i in range(int(np.sqrt(N)+0.5)):
  a = i+1
  if N % a != 0:
    continue
  step = a + int(N/a) -2
  if step < ans:
    ans = step
    
print(str(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N = int(input())
ans = 10^12
for i in range(int(np.sqrt(N))):
  a = i+1
  if N % a != 0:
    continue
  step = a + int(N/a) -2
  if step < ans:
    ans = step
    
print(str(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N = int(input())
ans = 10^12
for i in range(int(np.sqrt(N))):
  a = i+1
  if N % a != 0:
    continue
  step = a + N/a -2
  if step < ans:
    ans = step
    
print(str(ans))

Submission status: Wrong Answer

Solution code:
pn=[2]
A=1000
for L in range(3,A):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)
print(pn)

Submission status: Wrong Answer

Solution code:
import random
def p(n):
    r = []
    a, b = 0, 2
    while b * b <= n:
        if n % b == 0:
            n //= b
            r += [b]
        else:
            b += 1 + a
            a = 1
    if n > 1 : r += [n]
    return r
n = int(input())
m = p(n)
ans = n-1
for i in range(512):
    random.shuffle(m)
    a = 1
    b = n
    for i in m:
        if a >= b : break
        b //= i
        a *= i
    ans = min(ans, a+b-2)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import random
def p(n):
    r = []
    a, b = 0, 2
    while b * b <= n:
        if n % b == 0:
            n //= b
            r += [b]
        else:
            b += 1 + a
            a = 1
    if n > 1 : r += [n]
    return r
n = int(input())
m = p(n)
ans = n-1
for i in range(512):
    random.shuffle(m)
    a = 1
    b = n
    for i in m:
        if a > b : break
        b //= i
        a *= i
    ans = min(ans, a+b-2)
print(ans)

Submission status: Wrong Answer

Solution code:
def p(n):
    r = []
    a, b = 0, 2
    while b * b <= n:
        if n % b == 0:
            n //= b
            r += [b]
        else:
            b += 1 + a
            a = 1
    if n > 1 : r += [n]
    return r
b = int(input())
m = p(b)
if len(m) == 1:
    print(m[0]-1)
else:
    a = 1
    for i in m:
        if a > b : break
        b //= i
        a *= i
    print(a+b-2)

Submission status: Wrong Answer

Solution code:
import numpy as np

x = int(input())

for i in reversed(range(1, int(np.sqrt(x)))):
    if x%i==0:
        print(int(i+x/i-2))
        break

Submission status: Wrong Answer

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

result = sys.maxsize

for i in range(1,n):
  if a%i==0:
    b=a/i
    m = i+b-2
    if result>m:
      result = m
      
print(int(result))

Submission status: Wrong Answer

Solution code:
import math
import sys
a = int(input())
n = int(math.sqrt(a))
print(n)

result = sys.maxsize

for i in range(1,n):
  if a%i==0:
    b=a/i
    m = i+b-2
    print(i,b,m)
    if result>m:
      result = m
      
print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())

min_i = 1
min_j = N

for i in range(2, int(N**0.5)):
    if N%i==0:
        j = N / i
        
        if i + j < min_i + min_j:
            min_i = i
            min_j = j
            
print(int(min_i+min_j-2))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
time = []
jug = n - 1
for i in range(1, int(math.sqrt(n))):
    if n % i == 0:
        jug = min(jug, int(i + n / i - 2))
print(jug)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc144/tasks/abc144_c
# -*- coding: utf-8 -*-

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

input_val = int(input())
a = prime_factorize(input_val)

cnt_odd = 0
cnt_eve = 0

if len(a) == 0:
    print(0)
elif len(a) == 1:
    print(a[0]-1)
else:
    cnt_odd = a[0]
    cnt_eve = a[1]
    for i in range(2, len(a)):
        if i % 2 == 0:
            cnt_odd *= a[i]
        else:
            cnt_eve *= a[i]
    print(cnt_odd-1 + cnt_eve-1)

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

Solution code:
s = int(input())
dir = 1000000000000000000000
for i in range(1,int(s**0.5//1)):
	if s%i == 0:
		a = i
		b = s/i
		if a+b-2 < dir:
			dir = int(a + b - 2)
if s == 2:
  dir = 1
print(dir)

Submission status: Wrong Answer

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

ls = make_divisors(n)
#print(ls)

ans = 10**12
for i in range(1,len(ls),2):
    a = ls[i-1]
    b = ls[i]
    if a+b-2 < ans:
        ans = a+b-2
print(ans)

Submission status: Wrong Answer

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

ls = make_divisors(n)
#print(ls)

ans = 100000000000
for i in range(1,len(ls),2):
    a = ls[i-1]
    b = ls[i]
    if a+b-2 < ans:
        ans = a+b-2
print(ans)

Submission status: Wrong Answer

Solution code:
s = int(input())
a=0
b=0
dir = 1000000000000000000000
for i in range(1,int(s**0.5//1)):
	if s%i == 0:
		a = i
		b = s/i
		if a+b-2 < dir:
			dir = int(a + b - 2)
if s == 2:
  dir = 1
if s == 1:
  dir = 0
print(dir)

Submission status: Wrong Answer

Solution code:
s = int(input())
if s%2 == 0:
	ss = int(s/2)
else:
	ss = int(s/2)+1
a=0
b=0
dir = 1000000000000000000000
for i in range(1,ss):
	if s%i == 0:
		a = i
		b = s/i
		if a+b-2 < dir:
			dir = a+b-2
print(dir)

Submission status: Wrong Answer

Solution code:
n = int(input())
memory = []
result = n
for i in range(n):
    for j in range(n):
        if i * j == n:
            memory.append([i , j])
for k in memory:
    if result > sum(k):
        result = sum(k)
print(result -2)

Submission status: Wrong Answer

Solution code:
# ABC144c
import math


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    # map(int,input().split())
    n = int(input())
    ans = 10**12
    for i in range(n//2+1):
        for j in range(n//2+1):
            if(i*j == n):
                ans = min(ans, i+j)
    print(ans)


if __name__ == '__main__':
    main()