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:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

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

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

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

print(mn)

Submission status: Wrong Answer

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

import math

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

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

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

print(mn)

Submission status: Wrong Answer

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

import math

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

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

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

print(mn)

Submission status: Wrong Answer

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 = factorization(n)
#print(f)
a = 1
b = 1
check=0
for i in reversed(f):
    #print(i)
    for j in range(i[1]):
        tmp=i[0]
        if i[1]==0:
            continue
        else:
            if a < b:
                a *= tmp
                i[1]-=1
            else:
                b *= tmp

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

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
can=[]
for i in range(1,int(N**0.5)+1):
  if N%i==0:
    can.append(N-1+N//i-1)
    

print(min(can))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
lim = N
half_lim = int(math.sqrt(N)//1)
lis = [1  for i in range(0,half_lim+1,)]
for i in range(2,half_lim+1):
    for j in range(i,half_lim+1):
        if i*j > half_lim:
            break
        lis[i*j] = 0
result = N

for i in range(2,len(lis)):
    if lis[i] == 1:
        if N % i ==0:
            tmp = i-1  + (N//i -1)
            
            if result > tmp:
                result = tmp
    else :
        continue

if result ==N:
    print(result-1)
else :
    print(result)

Submission status: Wrong Answer

Solution code:
N=int(input())

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

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

mi = 10**10
for i in make_divisors(n):
    a = i;b = n//i
    mi = min(mi,a+b-2)

print(mi)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

def f(n):
    divisor = [1]
    limit = math.ceil(math.sqrt(n))
    for n2 in range(2, limit+1):
        if n % n2 == 0:
            divisor.append(n2)
    n1 = max(divisor)
    n2 = n // n1
    return n1 + n2 - 2

n = int(input())
f(n)

Submission status: Wrong Answer

Solution code:
def primelist(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def factorization(n):
    plist = primelist(int(n**0.5))
    factor = []
    for p in plist:
        k = 0
        while n%p==0:
            k+=1
            n//=p
        if k>0:
            factor.append((p,k))
        if n==1:
            break
    if n!=1:
        factor.append((n,1))

    return factor

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

divs = divisors(n)
t = len(divs)
if t==2:
  print(divs[-1]-1)
elif t%2==0:
  print(divs[t//2-1]+divs[t//2]-2)
else:
  print(divs[t//2]**2-2)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
a=int(math.sqrt(N))
while a>0:
  if N%a==0:
    print(a+N%a-2)
    break
  a-=1

Submission status: Wrong Answer

Solution code:
N = int(input().rstrip())
n = N
l = []
flag = True
while flag:
    flag = False
    for i in range(2,int(n**0.5)+3):
        if n % i == 0:
            l.append(i)
            n/=i
            flag = True
            break
    if n == 1:flag =False
num = len(l)
if num==0:
    print(N-1)
else:
    val = "".join(map(str,l))
    ans = N
    for j in range(2**num):
        s = format(j,'b').zfill(num)
        a=1
        for k in range(num):
            if s[k]!='0':
                a*=int(s[k])*int(val[k])
        b=int(N/a)
        ans = min([ans, a+b-2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

def factortwo(N):
    factors = []
    for i in range(1, int(math.sqrt(N))+1):
        if N % i == 0:
            factors.append((i, N // i))
    return factors

print(sum(factortwo(N)[-1]))

Submission status: Wrong Answer

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

min = N

for i in range(1,int(np.sqrt(N+1))):
    if N%i == 0:
        if (N//i - 1) + (i -1) > min:
            break
        else:
            min = (N//i - 1) + (i -1)

print(min)

Submission status: Wrong Answer

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

end = int(math.sqrt(10**12))
result = 10**9
for i in range(1,end+1):
    j = n//i
    if i * j == n:
        result = min(result,i+j-2)
print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
factors = []
while N % 2 == 0:
    factors.append(2)
    N //= 2
f = 3
while f*f <= N:
    if N % f == 0:
        factors.append(f)
        N //= f
    else:
        f += 2
if N > 1:
    factors.append(N)

if len(factors) == 1:
    print(N-1)
else:
    n = len(factors)
    sums = []
    for i in range(1, n**2-1):
        l = 1
        r = 1
        for j in range(n):
            if (i >> j) & 1:
                l *= factors[j]
            else:
                r *= factors[j]
        sums.append(l-1 + r-1)
    print(min(sums))

Submission status: Wrong Answer

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

minlen = 10**9
for i in range(1, int(math.sqrt(N))+1):
    if N%i == 0:
        minlen = min(minlen, i + N//i - 2)

if minlen == 10**9:
    print(N-1)
else:
    print(minlen)

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
N=int(input())
mem=make_divisors(N)
ans=(mem[(len(mem)//2)-1]+mem[(len(mem)//2)])-2
print(ans)

Submission status: Wrong Answer

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())
mem=factorization(N)
ans=0
while True:
    if ans*mem[-1][0]==N: break
    else: ans+=1
print((ans-1)+((mem[-1][0])-1))

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)
    return divisors

n = int(input())
divisor = make_divisors(n)
N = len(divisor)-1
ans = 10**13

for i in range(0,N,2):
    tmp = (divisor[i]-1)+(divisor[i+1]-1)
    ans=min(tmp,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())

list=[]

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

    if i>1 :
        if len(list) == 1:
            ans=(list[-1][0]-1)+(list[-1][1]-1)
            break
        if list[-1]==list[-2] or len(list)==1:
            ans=(list[-1][0]-1)+(list[-1][1]-1)
            break
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
n = int(input())
def factorization(num):
    result = []
    count = 0
    temp = num
    for i in range(2, int(num ** 0.5) + 1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp /= i
            result.append([i, count])
    if temp != 1:
        result.append([temp, 1])
    if result == []:
        result.append([num, 1])
    return result
factors = factorization(n)
exps = [range(factor[1] + 1) for factor in factors]
ans = 1001001001001
for exp0 in product(*exps):
    print(exp0)
    f0 = 1
    for i in range(len(exp0)):
        f0 *= factors[i][0] ** exp0[i]
    f1 = n // f0
    ans = int(min(ans, f0 + f1 - 2))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
n = int(input())
def factorization(num):
    result = []
    count = 0
    temp = num
    for i in range(2, int(num ** 0.5) + 1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp /= i
            result.append([i, count])
    if temp != 1:
        result.append([temp, 1])
    if result == []:
        result.append([num, 1])
    return result
factors = factorization(n)
exps = [range(factor[1] + 1) for factor in factors]
ans = 1001001001001
for exp0 in product(*exps):
    f0 = 1
    for i in range(len(exp0)):
        f0 *= factors[i][0] ** exp0[i]
    f1 = n // f0
    ans = min(ans, f0 + f1 - 2)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import math
import fractions
import functools
n = int(input())

maximum = math.ceil(math.sqrt(n))
minimum = 10**20
for i in range(1,maximum):
    j = 0
    if n % i == 0:
        j = n / i
        minimum = min(minimum,i+j)

print(int(minimum-2))

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
ans = n
for i in range(1, math.floor(math.sqrt(n))):
    if n % i == 0:
        ans = min(ans, i + n//i - 2)

print(int(ans))

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
ans = n
for i in range(1, math.floor(math.sqrt(n))):
    if n % i == 0:
        ans = min(ans, i + n/i - 2)

print(int(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
import math
for i in reversed(range(math.ceil(n**0.5))):
  if n%i==0:
    print(n//i+i-2)
    break

Submission status: Wrong Answer

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import math
    n=I()
    mini=1e+13
    for i in range(1,int(math.sqrt(n))):
        if n%i==0:
            mini=min(mini,i+(n//i)-2)
    print(mini)
    

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()

def get_divisors(n):
	divs = []
	for i in range(2, int(n**0.5)+1):
		c = 0
		while n % i == 0:
			n = n // i
			c += 1
		if c > 0:
			divs.append((i, c))
	if n > 0:
		divs.append((n, 1))
	return divs

divs = get_divisors(N)

a, b = 1, 1
while divs:
	d, c = divs.pop()
	for i in range(c):
		if a > b:
			b *= d
		else:
			a *= d
print(a+b-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
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()
print(divisors)
if len(divisors) % 2 == 1:
    print(2 * divisors[len(divisors) // 2] -2)
else:
    print(divisors[len(divisors) // 2] + divisors[len(divisors) // 2 - 1] - 2)

Submission status: Wrong Answer

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# C - Walk on Multiplication Table
import math


candidate = []

def plot_cal(x,y):
    x,y = x-1,y-1
    candidate.append(x+y)


def main():
    n = int(input())
    for i in range(1,math.ceil(n**0.5)):
        if n % i == 0:
            plot_cal(i,n//i)
    else:
        print(min(candidate))


if __name__ == "__main__":
    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)
  return divisors

N = int(input())
l = make_divisors(N)
a = l[len(l) - 1]
b = l[len(l) - 2]
print(a + b - 2)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
min_ = n-1
for i in range(1, math.floor(math.sqrt(n))+1):
  if n % i == 0:
    hosu = i+ n/i -2
    if hosu < min_:
      min_ = hosu
      
print(min_)

Submission status: Wrong Answer

Solution code:
# 対称性よりNの√を取り、1~√nまで全探索
import sys
input = sys.stdin.readline
 
N=int(input())
ans=10**12
for i in range(1,int(N**0.5)+1):
    if N%i==0: # 割り切れる場合
        ans=min(ans,i+N/i) # N//iはもう一個の解 N=i*N/i
print(ans-2) # -2はもともと(1,1)にいるからその分の差し引き

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import itertools
n = int(input())
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
x_max = 0
y_min = float('inf')
for it in itertools.combinations(divisor(n),2):
    if it[0] * it[1] == n:
        x_max = max(x_max,it[0])
        y_min = min(y_min,it[1])
print(x_max-1+y_min-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
divs = []
for i in range(1, int(n ** 0.5) + 1):
  if n % i == 0:
    divs.append(i)
    if i != n // i:
      divs.append(n // i)
sdivs = sorted(divs)
lsdivs = len(sdivs)
a = sdivs[lsdivs // 2 - 1]
b = sdivs[lsdivs // 2]
print(a + b - 2)

Submission status: Wrong Answer

Solution code:
n = int(input())
divs = []
for i in range(1, int(n**0.5) + 1):
  if n % i == 0:
    divs.append(i)
    if i != n // i:
      divs.append(n // i)
sdivs = sorted(divs)
lsdivs = len(sdivs)
a = sdivs[int(lsdivs / 2) - 1]
b = sdivs[int(lsdivs / 2)]
print(a + b - 2)

Submission status: Wrong Answer

Solution code:
import math


n = int(input())
a = math.sqrt(n)//1
while a > 0:
  if n%a == 0:
    s = a
    t = n//a    
    break
  a -= 1
print(s+t-2)

Submission status: Wrong Answer

Solution code:
def get_factors(N):
    """
    factor: Nの因数を返す.
    """
    if N<=1:
        return [N]
    factors = []
    while N%2==0:
        factors.append(2)
        N//=2
    tmp=3
    while tmp*tmp <= N:
        if N%tmp==0:
            factors.append(tmp)
            N//=tmp
        else:
            tmp+=2
    if N != 1:
        factors.append(N)
    return factors

def main():
    N=int(input())
    lst = get_factors(N)
    fst,snd=1,1
    for i in lst:
        if fst==min(fst,snd):
            fst*=i
        else:
            snd*=i
    print(fst+snd-2)

main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys
import math
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n=int(readline())

    to=int(math.sqrt(n))+1
    ans=9999999999999999999
    for i in range(2,to+1):
        if n%i==0:
            j=n//i
            ans=min(ans,i+j-2)
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:
from math import *

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

print(a[0][0]+a[0][1]-2)

Submission status: Wrong Answer

Solution code:
n = int(input())

m = 10**12
for i in range(2,int(n**0.5)+1):
    if n%i == 0:
        m = min(m,i+n//i-2)
    if i == int(n**0.5) -1:
        m = min(m,n-1)
if n <= 2:
    m = n
elif n == 3:
    m = 2
print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())

m = 10**12
for i in range(2,int(n**0.5)+1):
    if n%i == 0:
        m = min(m,i+n//i-2)
    if i == int(n**0.5) -1:
        m = min(m,n-1)
print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())

m = 10**12
for i in range(2,int(n**0.5)):
    if n%i == 0:
        m = min(m,i+n//i-2)
    if i == int(n**0.5) -1:
        m = min(m,n-1)
print(m)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

sys.setrecursionlimit(1000)

ten = 10 ** 6

def solve(N):
    # prime factor
    pf = defaultdict(int)
    for i in range(2,ten+1):
        if N % i == 0:
            while  N % i == 0:
                pf[i] += 1
                N = N // i
        
        # N dont have prime factor
        if N == 1 :
            break

    # N is prime number
    if not pf :
        print(N-1)
        sys.exit()

    a , b , flag = 1 ,1 ,1 
    for i in range(2,ten+1):
        if i in pf :
            if pf[i] % 2 == 0:
                a *= i ** (pf[i] // 2) 
                b *= i ** (pf[i] // 2) 
            else:
                if flag == 1 :
                    a *= i ** (pf[i] // 2 + 1) 
                    b *= i ** (pf[i] // 2) 
                    flag *= -1
                else:
                    b *= i ** (pf[i] // 2 + 1) 
                    a *= i ** (pf[i] // 2) 
                    flag *= -1
    
    print(a+b-2)


if __name__ == "__main__":
    N = int(input())
    solve(N)

Submission status: Wrong Answer

Solution code:
N = int(input())

for i in range(1, 1000000):
    if (N / i).is_integer():
        a = N // i
        b = N // a
        break

print(a+b-2)

Submission status: Wrong Answer

Solution code:
# C - Walk on Multiplication Table

N = int(input())
start = [1, 1]
end = [0, 0]
for i in range(1, int(N ** (1 / 2))):
    if N % i == 0:
        end[0] = i
        end[1] = N // i

print((end[0] - start[0]) + (end[1] - start[1]))

Submission status: Wrong Answer

Solution code:

import math
from collections import Counter
n = int(input())

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(n))+1):
  while n % i == 0:
    n /= i
    prime_count[i] += 1
if n > 1:
  prime_count[int(n)] += 1  

a, b = 1, 1
for k, v in prime_count.items():
  if v % 2 == 0:
    a *= k**(v//2)
    b *= k**(v//2)
  else:
    if a <= b:
      a *= k**(v//2+1)
      b *= k**(v//2)
    else:
      b *= k**(v//2+1)
      a *= k**(v//2)

print(a+b-2)

Submission status: Wrong Answer

Solution code:
import math

def main():
    n = int(input())
    m = math.sqrt(n)
    ans = []
    for i in range(1, int(m) + 1):
        div = n / i
        if not float.is_integer(div):
            continue
        ans.append((div+i)-2)

    print(min(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

def main():
    n = int(input())
    m = math.sqrt(n)
    ans = []
    for i in range(int(n) + 1):
        div = i / n
        if not float.is_integer(div):
            continue
        ans.append((div+i)-2)
    print(min(ans))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
keep=10**100
for i in range(1,10**6+1):
  if n%i==0:
    temp=i+n//i
    if temp<keep:
      keep=temp
print(temp-2)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

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())
yakusuu = make_divisors(n)
c = list(itertools.combinations(yakusuu, 2))
seki = np.prod(c, axis=1)==n
x = np.sum(c,axis=1)[seki]

print(min(x)-2)

Submission status: Wrong Answer

Solution code:
N=int(input())

from itertools import combinations

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

    # divisors.sort()
    return divisors

d=make_divisors(N)

c= list(combinations(d,2))

Candidate = []        

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

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

print(dist)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

Submission status: Wrong Answer

Solution code:
import math as m

n = int(input())
q = int(m.sqrt(n))

for i in range(q,0,-1):
    if n%i == 0:
        k = i
        l = n/i
        break

print(int(k+l-2))
print(q)

Submission status: Wrong Answer

Solution code:
import math
import itertools
n = int(input())
x = 1
for i in reversed(range(1, math.ceil(math.sqrt(n)))):
    if n % i == 0:
        x = n / i
        break

print(math.floor(x - 1 + n / x - 1))

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
x = 1
for i in reversed(range(1, math.floor(math.sqrt(n)))):
    if n % i == 0:
        x = n / i
        break

print(math.floor(x - 1 + n / x - 1))

Submission status: Wrong Answer

Solution code:
import math
import itertools
n = int(input())
x = 1
for i in reversed(range(1, int(math.sqrt(n)))):
    if n % i == 0:
        x = n / i
        break

print(x - 1 + n / x - 1)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = int(math.sqrt(N))
B = 10**12
ans = 10**6
for i in range(1,A+1):
    if N % i == 0:
        C = i + (N//i) - 2
        if C < ans:
            ans = C
print(ans)

Submission status: Wrong Answer

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

for i in range(1,int(N**(1/2))):
    b=N//i
    if N%i==0:
        a=i+b-2
print(int(a))

Submission status: Wrong Answer

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

for i in range(1,int(N**(1/2))):
    b=N//i
    if N%i==0:
        a=i+b-2
print(a)

Submission status: Wrong Answer

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

ans = 10**12+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:
def q3():
    import math
    N = int(input())

    ans = float('INF')
    for i in range(1, math.ceil(math.sqrt(N))):
        if N % i == 0:
            a = i
            b = N // i
            ans = min(ans, (a-1)+(b-1))
    print(ans)


if __name__ == '__main__':
    q3()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

N = int(input())

prime = prime_factorize(N)

if len(prime) == 1:
  print(prime[0] - 1)
elif len(prime) == 2:
  print(sum(prime) - 2)
elif len(prime) >= 3:
  
  if len(prime) % 2 == 0:
    while len(prime) > 2:
      tmp = prime[1:-1]
      tmp.append(prime[0] * prime[-1])
      prime = sorted(tmp)
  else:
    while len(prime) > 2:
      if len(prime) % 2 == 0:
        tmp = prime[1:-1]
        tmp.append(prime[0] * prime[-1])
        prime = sorted(tmp)
      else:
        max_num = prime[-1]
        prime = prime[:-1]
        tmp = prime[1:-1]
        tmp.append(prime[0] * prime[-1])
        tmp.append(max_num)
        prime = sorted(tmp)

  print(sum(prime) - 2)

Submission status: Wrong Answer

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

N = int(input())

prime = prime_factorize(N)

if len(prime) == 1:
  print(prime[0] - 1)
elif len(prime) == 2:
  print(sum(prime) - 2)
elif len(prime) >= 3:
  
  if len(prime) % 2 == 0:
    while len(prime) > 2:
      tmp = prime[1:-1]
      tmp.append(min(prime) * max(prime))
      prime = tmp
  else:
    while len(prime) >= 3:
      if len(prime) % 2 == 0:
        tmp = prime[1:-1]
        tmp.append(prime[0] * prime[-1])
        prime = sorted(tmp)
      else:
        max_num = prime[-1]
        prime = prime[:-1]
        tmp = prime[1:-1]
        tmp.append(prime[0] * prime[-1])
        tmp.append(max_num)
        prime = sorted(tmp)

  print(sum(prime) - 2)

Submission status: Wrong Answer

Solution code:
import math

N = 10000000019
N = 50
N = 10
N = int(input())

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

print(min(result))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import numpy as np
 
n = int(input())
ans = np.inf
for i in range(1, int(math.sqrt(n))+1):
    if n%i==0:
        q = n/i 
        tmp = i+q 
        if tmp <= ans:
            ans = tmp 
print(ans)
print(int(ans-2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import numpy as np

n = int(input())
ans = np.inf
for i in range(1, int(math.sqrt(n))+1):
    if n%i==0:
        q = n//i
        tmp = i+q 
        if tmp <= ans:
            ans = tmp 
            i_ = i 
            q_ = q 

if i_ == 1 or q_ == 1:
    print(ans-1)
else:
    print(ans-2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import numpy as np

n = int(input())
ans = np.inf
for i in range(1, int(math.sqrt(n)+1)):
    if n%i==0:
        q = n//i
        tmp = i+q 
        if tmp <= ans:
            ans = tmp 
            i_ = i 
            q_ = q 

if i_ == 1 or q_ == 1:
    print(ans-1)
else:
    print(ans-2)

Submission status: Wrong Answer

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