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: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
import os
import itertools

n = int(input())

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

a, b = is_prime(n)
if a:
    print((a-1)+(b-1))
else:
    print(n-1)

Submission status: Runtime Error

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

n = make_divisors(N)

cnt = 999999999999
for i in range(0,len(n),2):
    t = n[i]-1 + n[i+1]-1
    if cnt > t:
        cnt = t
print(cnt)

Submission status: Runtime Error

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: Runtime Error

Solution code:
n = int(input())

ans = n
for i in range(n):
  if n % i == 0:
    b = n/i + i -2
    if b < ans:
      ans = b
print(ans)

Submission status: Runtime Error

Solution code:
a=int(input())

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

res=make_divisors(a)
my_min=0
for i in range(len(res)):
    if i==0:
        if len(res[i])==2:
            my_min=res[i][0]+res[i][1]
        else:
            my_min=(res[i]*2)
    else:
        if len(res[i])==2:
            my_min=min(my_min,res[i][0]+res[i][1])
        else:
            my_min=min(my_min,res[i]*2)

print(my_min-2)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
min = math.inf
for i in range(1, 1000000):
    if N % i == 0:
        val = i + int(N / i) - 2
    if min > val:
        min = val

print(min)

Submission status: Runtime Error

Solution code:
import numpy as np

A = int(input())

candidates = np.arange(A // 2) + 1
candidates = candidates[A % candidates == 0]

distances = (A // candidates) - 1 + candidates - 1

print(np.min(distances))

Submission status: Runtime Error

Solution code:
import sys
f = open('q1input.txt', 'r')
sys.stdin = f


# Setup
import sys
sys.setrecursionlimit(4100000)

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(n)
    return table

a = int(input())
b = prime_decomposition(a)
b.sort()
if len(b) == 1:
    print(a-1)
else:
    ax = b[0]
    ay = b[1]
    for i in range(2,len(b)):
        if ax < ay:
            ax *= b[i]
        else:
            ay *= b[i]
    print(int(ax+ay-2))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
index = 2
result = math.inf
while index * index <= n:
    if n % index == 0:
        curr = (n // index) - 1
        curr += (index - 1)
        result = min(curr, result)
    index += 1
if result == math.inf:
    result = n - 1
print(result)

Submission status: Runtime Error

Solution code:
N = int(input())
k = 0
while k ** 2 < N:
  k++
for i in range(k, 0, -1):
  if N % i:
    continue
  print(N // i + i - 2)
  break

Submission status: Runtime Error

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())
ls = prime_factorize(n)

for i in range(len(ls) //2 + 1):
  ans = []
  ans.append(i + n / i - 2)

ans.sort()
print(ans[0])

Submission status: Runtime Error

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])
    ans = min(ans, x[i] - 1 + x[i+1] - 1)
  print(ans)
  

main()

Submission status: Runtime Error

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())
datas=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: Runtime Error

Solution code:
import math
N = int(input())
M = int(math.sqrt(N))
i = 1
j = 1
for x in reversed(range(M)):
  if N % x == 0:
    i = x
    j = N // x
    break
print(i+j-2)

Submission status: Runtime Error

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