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:
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
A = factorization(N)
flag = True

x = 1
y = 1

for a in A:
    for i in range(a[1]):
        if flag:
            x *= a[0]
            flag = False
        else:
            y *= a[0]
            flag = True
print(x-1 + y-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = N
i = 1
while i**2 <= N:
    if N % i == 0:
        s = i
    i += 1

ans = N/s + s - 2
print(ans)

Submission status: Wrong Answer

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


n=one_int()

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



sums = 0
for i in divisors:
    if i!=1:
        sums+=(i-1)
print(sums)

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

def main():
    N = int(input())

    A = prime_factorize(N)
    if len(A) == 1:
        print(sum(A)-1)
    elif len(A) == 2:
        print(sum(A)-2)
    else:
        x = 1
        y = 1
        for a in A:
            if x >= y:
                y *= a
            else:
                x *= a

        print(x+y-2)


if __name__ == '__main__':
    main()

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
    
divisors = make_divisors(N)

x_ax = divisors[-2] - 1
y_ax = divisors[-1] - 1

print(x_ax + y_ax)

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())
A=prime_factorize(n)
x,y=1,1
for i in A[::-1]:
    if x<y:x *=i
    else:y *=i
print(x+y-2)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=1
while(n%2==0):
    a*=2
    n//=2
for i in range(3,int(math.sqrt(n))+1):
    if n%i==0:
        if a*i>n//i:
            break
        a*=i
        n//=i
print(a-1+n-1)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
sq_n=int(math.sqrt(n))
ans=n-1
for i in range(int(sq_n/2)+2):
    tmp=2*i+3
    if n%tmp==0:
        ans=min(ans, tmp+n//tmp-2)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

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

def main():
  n = ni()

  x = divi(n)
  
  ans = 1e18+7
  for i in range(0, len(x), 2):
    # print(x[i])
    try:
        ans = min(ans, x[i] - 1 + x[i+1] - 1)
    except:
        break
  print(ans)
  

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
tmp = []
for i in range(1,N+1):
  if N % i == 0:
    tmp.append(i + N/i)
print(min(tmp) - 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())
data=prime_factorize(N)
a=1
b=1
for i in range(len(data)):
  if a<b:
    a*=data[i]
  else:
    b*=data[i]

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

list1 = prime_factorize(n)

length = math.ceil(len(list1)/2)

a,b = 1,1
for i in range(length):
	a *= list1[i]
for i in range(length,len(list1)):
	b *= list1[i]

print((a-1)+(b-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)

    divisors.sort()
    return divisors

t = make_divisors(N)
i = len(t) // 2 - 1 
print(t[i] + t[i+1] - 2)

Submission status: Wrong Answer

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


n=one_int()

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



sums = 0
for i in divisors:
    if i!=1:
        sums+=(i-1)
    else:
        sums+=1
print(sums)

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

import collections
import numpy as np

# = input()
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
#

N = int(input())

yakusu = make_divisors(N)
yakusu.sort()
ans = np.inf
for y in yakusu:
  if y + N // y < ans:
    ans = (y + N // y) - 2

    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
ans=10**12
sqrt_n=math.ceil(math.sqrt(n))
for i in range(1,sqrt_n):
    if(n%i==0 and ans > i+(n//i)-2):
        ans = i + (n//i) - 2
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
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())
tmp = make_divisors(N)
print(sum(tmp[-2:]) - 2)

Submission status: Wrong Answer

Solution code:
# coding:utf8
from collections import  Counter

n=int(input())

ans=10**12+1

def divisor(n): #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

t=divisor(n)
for i in range(0,len(t)//2):
    if i%2==0:
        tmp=t[i]+(n//t[i])-2
        ans=min(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = input()
    if n == 1:
        print(0)
        return
    factors = {}
    p = 2
    while n % p == 0:
        factors[p] = factors.get(p, 0) + 1
        n //= p
    p = 3
    while n >= p * p:
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
        p += 2
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    
    a = b = 1
    for f in sorted(factors, reverse=True):
        while factors[f] > 0:
            if a > b:
                b *= f
            else:
                a *= f
            factors[f] -= 1
    print(a + b - 2)

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
cost = []
i = 2
while i < n**0.5:
  if n % i == 0:
    cost.append(i+n/i-2)
  i += 1
if len(cost) == 0:
  cost.append(n-1)
print(int(min(cost)))

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())
a = make_divisors(n)
#もっとも近い約数を求める
mid = len(a)//2
#print(a)
#print(a[mid],a[mid-1])
ans = (a[mid-1]-1)+(a[mid]-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
a = int(input())
b = make_divisors(a)
b_len = len(b)
print(b[b_len//2-1] + b[b_len//2] - 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:
                x = (n//i)
                y = x + (n / x)
                divisors.append(y)

    divisors.sort()
    return divisors

n = int(input())

t = make_divisors(n)
print(int(t[0]-2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = 10**9

def prime_factorize(n, unique=False):
    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)
    if unique:
        return set(fct)
    else:
        return fct

n = int(input())
fact = prime_factorize(n)
fact.append(1)

ans = INF 
for item in fact:
    ans = min(ans, item + n // item - 2)
print(ans)

Submission status: Wrong Answer

Solution code:
def sim_fact(inp):
  n = 1
  pairs = []
  while n * n < inp:
    if inp % n == 0:
      pairs.append([n, inp//n])
    n += 1
  return pairs

pairs = sim_fact(int(input()))
print(min([sum(pair) for pair in pairs]) - 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

factors = prime_factorize(N)

a = 1
b = 1
for n in factors:
    if a <= b:
        a *= n
    else:
        b *= n
        
ans = a + b - 2
print(ans)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())

ans = n-1

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
ans=10**12
sqrt_n=math.ceil(math.sqrt(n))
for i in range(1,sqrt_n):
    if(n%i==0 and ans > i+(n//i)):
        ans = i + (n//i) - 2
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
a, = [list(map(int, s.split())) for s in open(0)][0]
min_ = a
for i in range(1,int(np.sqrt(a))):
    if a % i == 0:
        tmp = i + a//i - 2
        if tmp < min_:
            min_ = tmp
print(min_)

Submission status: Wrong Answer

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

for i in range(1, int(N ** 0.5)):
    if(N % i == 0):
        a = i

ans = 0
if (a == 0):
    ans = N - 1
else:
    ans = a + N // a - 2

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
a=1
while(n%2==0):
    a*=2
    n//=2
for i in range(3,int(math.sqrt(n))+1):
    if n%i==0:
        a*=i
        n//=i
print(a-1+n-1)

Submission status: Wrong Answer

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

ans = []

for i in range(1,10**6):
  if N % i == 0:
    ans += [i + N//i - 2]

print(min(ans))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7


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

n = int(input())
ans = 0
a = make_divisors(n)
print(a-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())
A=prime_factorize(n)
x,y=1,1
for i in A:
    if x<y:x *=i
    else:y *=i
print(x+y-2)

Submission status: Wrong Answer

Solution code:
N = int(input())
def make_div(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 sorted(divisors)
div = make_div(N)

minn = 100000000000000000000
for i in range(len(div)):
    for j in range(i+1, len(div)):
        if (div[i] * div[j]) == N and (div[i] + div[j]) < minn:
            minn = div[i] + div[j]

print(minn-2)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()

ans = MAX_INT
for i in range(1, int(math.sqrt(N))+1):
  if N%i == 0:
    tmp = N//i
    ans = min(ans, i + tmp -2)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def f(n):
    mx=0
    for i in range(2,int(math.sqrt(n))):
        if n%i==0:
            mx=i
    if mx==0:
        mx=1
    return mx

def main():
    N=int(input())
    fact1=f(N)
    return fact1+N//fact1-2

print(main())

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
a = prime_factorize(N)

i, j = N // max(a) - 1, max(a) - 1
print(i + j)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000)
INF = 1<<32


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

    l = primeFactorize(N)

    a = 1
    b = 1

    for i in range(len(l)):
        if(i%2 == 0):
            a *= l[i]
        else:
            b *= l[i]

    print(a+b-2)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
curmin = 10**13
for i in range(1,int(n**(1/2))):
    if (n%i==0 and n//i+i<curmin):
        curmin = n//i+i

print(curmin-2)

Submission status: Wrong Answer

Solution code:
N=int(input())

li=[]
for i in range(1,int(N**0.5)+1):
  if N%i==0:
    li.append(i+N//i)
print(min(li))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
sqrt = math.ceil(n ** 0.5)
a = 1 + n
for i in range(2, sqrt):
  if n % i == 0:
    a = min(a, i + n // i)
print(a - 2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def calc(x):
    ret = (1, x)
    for i in range(1, 10**6):
        if i*i > x:
            break
        if x % i == 0:
            if i + x //i < ret[0]+ret[1]:
                ret = (i, x//i)
    return ret

def main():
    n = ri()
    ret = calc(n)
    print(ret[0]+ret[1]-2)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

p = prime_factorization(N)
a = b = 1
for i, v in enumerate(p):
    if i % 2:
        a *= v
    else:
        b *= v
print(a+b-2)

Submission status: Wrong Answer

Solution code:
N = int(input())
from math import sqrt
res = set()
for i in range(int(sqrt(N)+1),0,-1):
  if N%i==0:
    print(i)
    res |= {N//i+i-2}
print(min(res))

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

a = prime_factorize(n)
b = 1
c = 1
for i in range(len(a)):
  if i % 2 == 0:
    b *= a[i]
  else:
    c *= a[i]
ans = b-1+c-1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from fractions import gcd

def trial_division(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    if not factor:
        return [1, n]
    else:
        factor.append(n)
        return factor

n1 = int(input())
n2 = trial_division(n1)

c1 = 1
c2 = 1

for i1 in range(len(n2)):
    if c1 < c2:
        c1 = c1 * n2[i1]
    else:
        c2 = c2 * n2[i1]

r1 = c1 + c2 - 2
print(r1)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n = INT()
    if n == 1:
        print('Yes')
        sys.exit()
    for i in range(2, 10):
        if n % i ==0:
            if n / i < 10:
                print('Yes')
                sys.exit()

    print('No')

if  __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
Alist = []
Blist = []

for i in range(1,10**6):
    if N%i==0:
        Alist.append(int(i)+int(N//i)-2)

print(min(Alist))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	ans = INF
	for i in range(1, 10 ** 6):
		if N % i == 0:
			ans = min(ans, i + int(N // i) - 2)
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def main():
    n = int(input())
    ans = float("inf")
    for i in range(1,1000000):
        if n % i == 0:
            ans = min(i-1 + n//i-1,ans)
    print(ans)





    
            
    

    

    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

T = trial_division(N)
T = sorted(T)

ans = float("inf")

for i in range(len(T)) :
    a = T[i]
    b = N//a
    ans = min(ans, a+b-2)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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

k = make_divisors(n)


print(k[-1]-1 + k[-2] - 1)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
input = sys.stdin.readline

setrecursionlimit(1000000)

dp = defaultdict(lambda x:-1)

def main():
	n = int(input())
	i = int(math.sqrt(n)) + 1
	while True:
		if(n % i == 0):
			print(n//i + i - 2)
			return
		i += 1

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 zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

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

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = float("INF")
for i in range(1, 100010):
  if (n%i == 0):
    j = n//i
    ans = min(ans, i+j-2)
print(ans)

Submission status: Wrong Answer

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

for i in range(1, int(N ** 0.5)):
    if(N % i == 0):
        a = i

ans = 0
if (a == 0):
    ans = N -1
else:
    ans = a + N // a

print(ans - 2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = float("inf")
for i in range(1, 10**6):
    q, m = divmod(N, i)
    if m==0:
        ans = min(ans, q+i)
print(ans-2)

Submission status: Time Limit Exceeded

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

    ans = 10**12
    for i in range(2**(len(c))):
        x,y = 1,1
        for j in range(len(c)):
            if i>>j&1:
                x *= c[j]
            else:
                y *= c[j]
        ans = min(ans,x+y-2)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def division(n):
    a = [1]
    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())
c = division(n)

ans = 10**12
for i in range(2**(len(c))):
    x,y = 1,1
    for j in range(len(c)):
        if i>>j&1:
            x *= c[j]
        else:
            y *= c[j]
    ans = min(ans,x+y-2)
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())

# N = i*jをみつける
# (i, j)


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

def remove_dup_list(tmplist):
    return map(list, set(map(tuple, tmplist)))


prime_list = prime_factorize(N)

if len(prime_list)<=1:
    result = N-1
else:
    result = 10**12


#print(prime_list)
for i in range(len(prime_list)//2):
    # i個抽出
    tmp = list(itertools.combinations(prime_list, i+1))
    tm = remove_dup_list(map(list, tmp))
    #print(tm)
    for _ in tm:
        temp_origin_list = copy.copy(prime_list)
        for item in _:
            temp_origin_list.remove(item)
        result = min(result, reduce(mul, _) + reduce(mul, temp_origin_list) - 2)

print(result)

Submission status: Time Limit Exceeded

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

N = int(input())

# N = i*jをみつける
# (i, j)


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

def remove_dup_list(tmplist):
    return list(map(list, set(map(tuple, tmplist))))


prime_list = prime_factorize(N)


#print(prime_list)


import copy
if len(prime_list)<=1:
    result = N-1
else:
    result = 10**12


    
for i in range(len(prime_list)//2):
    # i個抽出
    tmp = list(itertools.combinations(prime_list, i+1))
    tm = map(list, tmp)
    tm = remove_dup_list(tm)
    for _ in tm:
        temp_origin_list = copy.copy(prime_list)
        for item in _:
            temp_origin_list.remove(item)
        #print(_, temp_origin_list)
        result = min(result, reduce(mul, _) + reduce(mul, temp_origin_list) - 2)
print(result)