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:
target = int(input())
curAns = 10 ** 12

for i in range(1,10):
  if target % i == 0:
    j = target // i
    if (i+j-2) < curAns:
      curAns = i+j-2
print(curAns)

Submission status: Wrong Answer

Solution code:
N = int(input())
yaku = 1

import math

    



if N % 2 == 0:
	yaku = 2
	
for i in range(3,int(math.sqrt(N)),2):
	if N % i == 0:
		yaku = i
		

yaku2 = int(N/yaku)

print(int(yaku2+yaku - 2))

100000

Submission status: Wrong Answer

Solution code:
n=int(input())
z=0
if (int(2*(n**0.5)))<(2*(n**0.5)):
    z=((int(2*(n**0.5)))+1)
else:
    z=(int(2*(n**0.5)))
print(z-2)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())

ns = [int(i) for i in str(n)]
a = 0
b = 0
ans = 0
f = 0

# def search():
#     for i in range(int(math.sqrt(n)),0,-1):
#         print(i)
#         if n % i == 0:
#             a = i
#             b = n // i
#             break
#     else:
#         ans = n - 1

if ns[-1] % 2 == 0 or sum(ns) % 3 == 0 or ns[-1] == 5:
    y = math.sqrt(n)
    for i in range(int(y),0,-1):
        if n % i == 0:
            a = i
            b = n // i
            break
    else:
        ans = n - 1
        f = 1
else:
    z = math.sqrt(n)
    for i in range(7,int(z),2):
        if n % i == 0:
            a = i
            b = n // i
            break
        else:
            ans = n - 1
            f = 1

# print('a',a)
# print('b',b)

if f:
    print(ans)
else:
    ans = a - 1 + b - 1
    print(ans)

Submission status: Wrong Answer

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


def solve(N):
    list_N = divisor(N)
    ans = N - 1
    print(list_N)
    for i in list_N:
        ans_tmp = ((N / i) - 1) + (i - 1)
        if ans > ans_tmp:
            ans = ans_tmp

    return ans


print(solve(N))

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)

ans = N
tmp = [1, N]

for b in a:
    tmp = [tmp[0] * b, tmp[1]//b]
    if ans > tmp[0] + tmp[1] - 2:
        ans = tmp[0] + tmp[1] - 2
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.spatial.distance import cityblock

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():
  N = int(input())
  x = make_divisors(N)
  ans = []
  p = int(len(x)/2)
  if p%2 != 0:
    ans.append(cityblock((1,1),(x[p],x[p])))
  for i in range(p):
    ans.append(cityblock((1,1),(x[i],x[len(x)-1-i])))
  print(min(ans))

main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul

N = int(input())

def main():
    primes = prime_factorize(N)
    if len(primes) == 1:
        print(primes[0] - 1)
        return
    elif len(primes) == 2:
        print(primes[0] + primes[1] - 2)
        return

    a = 1
    b = 1
    for p in primes:
        if a <= b:
            a *= p
        else:
            b *= p

    print(a + b - 2)

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

main()

Submission status: Wrong Answer

Solution code:
def min_sumlis(li):
    li.sort()
    while len(li) > 2:
        li.insert(0, li[0] * li[1])
        li.remove(li[1])
        li.remove(li[1])
    print(sum(li)-2)


def Factor(number):
    lis = []
    lis.append(1)
    while number % 2 == 0:
        lis.append(2)
        number = int(number / 2)
    for num in range(2, number+1):
        while number % num == 0:
            lis.append(num)
            number = number / num
    min_sumlis(lis)


Factor(int(input()))

Submission status: Wrong Answer

Solution code:
"""
N = int(input())
ans = 10000000020
for i in range(1,N+1):
    if N % i == 0:
        tmp = int((N / i) + i)
        tmp -= 2
        if tmp < ans:
            ans = tmp

print(ans)
"""
# 平方根の計算や切り上げを行う
import math

N = N = int(input())

# 素数ならTrue
flg = True

# 検索する最大値
max_search = math.ceil(math.sqrt(N))

if N <= 3:
  # 3以下なら素数
  pass
else:
  for i in range(2, max_search):
    if N % i == 0:
        flg = False
        break
ans = 10000000020
# メッセージを表示
if flg:
  print(N -1)
else:
    ans = 10000000020
    for i in range(1,N+1):
        if N % i == 0:
            tmp = int((N / i) + i)
            tmp -= 2
            if tmp < ans:
                ans = tmp

    print(ans)

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

n = int(input())

if is_prime(n) == True:
    print(n-1)
else:
    for i in range(1,round(n/2)):
        if n % i == 0:
            ans = i
        
        
    ans2 = round(n/ans)
    print(ans+ans2-2)

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
n2.sort(reverse = True)

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:
n = int(input())
count = True
tmp = 1
output = n - 1

while count:
    for i in range(2, 100):
        if n % i == 0:
            tmp *= i
            n //= i
            if (n - 1) + (tmp - 1) < output:
                output = (n - 1) + (tmp - 1)
            break

        count = False

print(output)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import sqrt

N = int(input())

it = int(sqrt(N))

for i in range(it, 0, -1):
    remain = N % i
    if remain == 0:
        shou = N / i

        if shou:
            print(i+shou-2)
            break

Submission status: Wrong Answer

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

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())
d = make_divisors(n)
a = []
for i in range(len(d)-1):
  for j in range(i+1, len(d)):
    if d[i] * d[j] == n:
      a.append([d[i], d[j]])
m = n
ind = 0
for i in a:
  if abs(i[0]-i[1]) < m:
    m = abs(i[0]-i[1])
    ind = a.index(i)
    
print(a[ind][0]+a[ind][1]-2)

Submission status: Wrong Answer

Solution code:
n = int(input())
min = n+1
kaisu = int((n/2)-1)

for i in range(kaisu):
    if n%(i+1)==0:
        tmp = i+(n/(i+1))-1
        if min > tmp:
            min = tmp
    if (i+1)**2>n:
        break

print(int(min))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
p = int(math.sqrt(N))

def search(N, p):
#     print(p)
    if N % p == 0:
        q = int(N / p)
        return p, q
    else:
        if p * N // p > N:
            p, q = search(N, p - 1)
        else:
            p, q = search(N, p + 1)
    
    return p, q

try:
    p, q  = search(N, p)
    print(p + q - 2)
except:
    print(N - 1)

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


    arr.append([n, 1])

    return arr
  
N = int(input())
A = factorization(N)
ans =[]
for a in A:
  for i in range(a[1]):
    ans.append(N//a[0]+a[0]-2)

print(int(min(ans)))

Submission status: Wrong Answer

Solution code:
import math
import fractions
import random
import functools

N = int(raw_input())

def lcg(n, c, x):
    '''
    a pseudorandom number generator (known as Linear Congruential Generator)
    '''
    return (x * x + c) % n


class memoize(object):
    '''
    a decorator function class to memoize a expensive function.
    '''
    def __init__(self, func):
        self._func = func
        self._cache = {}

    def __call__(self, *args):
        if self._cache.has_key(args):
            return self._cache[args]
        res = self._func(*args)
        self._cache[args] = res
        return res


@memoize
def is_prime(n, accuracy=20):
    '''
    check if `n` is probable prime using Rabin Miller method.
    to get more reliability, increase `accuracy` parameter.
    '''
    n = abs(n)
    if n == 2:
        return True
    if n == 1 or not n & 1:
        return False
    d = n - 1
    while not d & 1:
        d >>= 1
    for i in range(accuracy):
        a = random.randrange(n - 2) + 1
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1
        if y != n - 1 and not t & 1:
            return False
    return True


def trial_division(n):
    '''
    find the smallest divisor of the integer `n` with Trial Division method.
    returns -1 if it is a prime.
    '''
    limit = int(math.sqrt(n) + 1)
    for i in range(2, limit):
        if not n % i:
            return i
    return -1


def pollards_rho(n, c=1):
    '''
    find the one of divisors of the composite number `n` with Pollard's Rho method.
    returns -1 if it is a prime.
    to get another result, change `c` parameter.
    warning: less reliable for small composite numbers.
    '''
    x, y, d = 2, 2, 1
    f = functools.partial(lcg, n, c)
    while d == 1 and n:
        x = f(x)
        y = f(f(y))
        d = fractions.gcd(x - y, n)
        if d == n:
            return -1
    return d


@memoize
def factor(n, accuracy=10):
    '''
    factorize the integer `n`.
    returns list of prime factors.
    '''
    if is_prime(n):
        return [n]
    if n < 100:
        # fallbacks to trial division for a small integer
        divisor = trial_division(n)
    else:
        # `accuracy` is diverted to the constant of Pollard's Rho
        divisor = pollards_rho(n, accuracy)
    if divisor == -1:
        if accuracy:
            # repeat with another constant
            return factor(n, accuracy - 1)
        return [n]
    return factor(n / divisor) + factor(divisor)

def compose(xs):
    if len(xs) <= 1:
        return xs + [1]
    if len(xs) == 2:
        return xs
    return compose([xs[0] * xs[1]] + xs[2:])

factors = list(reversed(factor(N)))
i, j = compose(factors)
print (i - 1) + (j - 1)

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import itertools
def factorize(n):
    b = 2
    fct = []
    fct.append(1)
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

N = int(input())
listN = factorize(N)
x = 0
y = 0

mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(1,len(listN)):
        x0,y0 = 1,1
        tmp = list(itertools.combinations(listN,i))
        for j in range(len(tmp)):
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                y0 = N//x0
                if mini > abs(x0-y0):
                    mini = abs(x0-y0)
                    x = x0
                    y = y0

print(x-1+y-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)

    # divisors.sort()
    return divisors

N = int(input())

n = make_divisors(N)
n.sort()
mannaka_ = int(len(n)/2)
mannaka = mannaka_ - 1

if len(n) != 3:
    print((n[mannaka_]-1)+ (n[mannaka]-1))
else:
    print((n[mannaka_+1]-1)+ (n[mannaka]-1))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
k = math.sqrt(N)
z = math.floor(k)

if N%2 == 1:
    print(N-1)
elif z < k:
    r = (z*2) - 1
    print(r)
else:
    r = (z*2) - 2
    print(r)

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())
ans = 0
cols = prime_factorize(n)
cols.sort(reverse=True)
a = [1, 1]
for col in cols:
  ma = min(zip(a, range(len(a))))[1]
  a[ma] = a[ma] * col

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