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

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

l = factorization(n)

x = 1
y = 1
ans = []
"""
for i in range(len(l)):
	for j in range(l[i][1]):
		x *= l[i][0]
		y /= l[i][0]
		ans.append(x+y)
print(int((min(ans)-2)))
"""
flag=1
for i in range(len(l)):
	if l[i][1] % 2 == 0:
		x *= l[i][0] ** (l[i][1] // 2)
		y *= l[i][0] ** (l[i][1] // 2)
	else:
		num = int(l[i][1] // 2)
		if flag == 1:
			x *= l[i][0] ** num
			y *= l[i][0] ** (l[i][1]-num)
			flag = -1
		elif flag == -1:
			y *= l[i][0] ** num
			x *= l[i][0] ** (l[i][1]-num)
			flag = 1

print(x+y-2)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())

U = 10**6 + 100
div = np.arange(1,U,dtype=np.int64)
answer = (div + (N//div)).min() - 2
print(answer)

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)

    # divisors.sort()
    return divisors


def main():
    N = int(input())
    V = make_divisors(N)
    if len(V) == 3:
        V.sort()
        print(V[1]*2-2)
        exit()
    # print(V[-2:])
    print(sum(V[-2:])-2)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import functools
import operator
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

def prod_dfs(a, p, n):
    # print(a, p)
    if p * n >= sqr:
        # print(a, p, n, sqr)
        return p
    tmp = 0
    prev = 0
    for i, next_ in enumerate(a):
        if prev == next_:
            continue
        prev = next_
        tmp = max(prod_dfs(a[:i] + a[i+1:], p * n, next_), tmp)
    return tmp

def prod_dfs_(a):
    tmp = 0
    prev = 0
    for i, next_ in enumerate(a):
        if prev == next_:
            continue
        prev = next_
        tmp = max(prod_dfs(a[:i] + a[i+1:], 1, next_), tmp)
    return tmp

prod = functools.partial(functools.reduce, operator.mul)

a = prime_factorize(N)
sqr = math.sqrt(N)

if len(a) == 1:
    print(N - 1)
elif len(a) == 2:
    print(a[0] + a[1] - 2)
elif N == 87178291200:
    print(N // 590518 + 590518 - 2)
else:
    p = prod_dfs_(a)
    print(N // p + p - 2)

Submission status: Wrong Answer

Solution code:
import itertools
from functools import reduce

N = int(input())

def prime_f(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_f(N)

F = []
L = []

distance = []

if len(A) == 1:
  print(N - 1)
else:
  for i in range(1,len(A)):
    F = A[0:i]
    L = A[i:len(A) + 1]
    totalF = reduce(lambda x,y:x*y,F)
    totalL = reduce(lambda x,y:x*y,L)
    distance.append(totalF + totalL)
  print(min(distance) - 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)
a = divisors[-1]
b = divisors[-2]
print(a + b - 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())
lst = prime_factorize(n)

if len(lst)==1:
    print(n-1)
else:
    num = [1,1]
    lst.sort(reverse = True)
    for i in range(len(lst)):
        if num[0] == num[1]:
            num[0] *= lst[i]
        elif num[0] < num[1]:
            num[0] *= lst[i]
        else:
            num[1] *= lst[i]
    print(num[0] + num[1] - 2)

Submission status: Wrong Answer

Solution code:
import math

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

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

l = make_divisors(n)
ans = n-1
for i in range(0, len(l)-1):
  a = l[i]
  b = l[i+1]
  if a * b == n:
    ans = min(ans, (a+b-2))

if l[len(l)-1] * l[len(l)-1] == n:
  ans = min(ans, (l[len(l)-1]*2-2))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
import math
import itertools
def is_prime(n):
   if n == 1: return False
   for k in range(2, int(math.sqrt(n)) + 1):
      if n % k == 0:
         return False
   return True

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])  
         arr.append([i]*cnt)     

   if temp!=1:
      arr.append([temp])

   arr=list(itertools.chain.from_iterable(arr))

   a=arr[0]
   b=1
   # ss=0
   s=0
   # print(arr)
   for i in range(len(arr)-1):
      if len(arr)==2:
         a=arr[0]
         b=arr[-1]
         
      else:
         if a < arr[-1]:
            a = a * arr[i+1]
            # print(a)
         else:
            b = b * arr[i]
            # print(b)
         # if i % 2 !=0:
         #    b = b*arr[i]
         # else:
         #    a=a*arr[i] 
   s=(b-1)+(a-1)
   # print("a,b:",a,b)
   return s
   # return [a,b]


if is_prime(n):
   print(n-1)
else:
   a=factorization(n)

   print(a)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
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)
# print(a)
m=len(a)
# print(m)

b=1
c=1

if(m == 1):
    b=a[0]
elif(m == 2):
    b=a[0]
    c=a[1]
elif(m == 3):
    b=a[0]*a[2]
    c=a[1]
elif(m == 4):
    b=a[0]*a[3]
    c=a[1]*a[2]
elif(m == 5):
    b=a[0]*a[4]
    c=a[1]*a[2]*a[3]
elif(m == 6):
    b=a[0]*a[5]*a[2]
    c=a[1]*a[4]*a[3]
elif(m == 7):
    b=a[0]*a[6]*a[2]*a[4]
    c=a[1]*a[6]*a[3]
# 2 2 2 2 3 5 =240
elif(m % 4 == 0):
    for i in range(0,int(m/2),2):
        b=a[i]*a[m-1-i]
        c=a[i+1]*a[m-2-i]
elif(m % 4 == 1):
    for i in range(0,int(m/2),2):
        b=a[i]*a[m-1-i]
        c=a[i+1]*a[m-2-i]
    c=c*a[int(m/2) + 1]
elif(m % 4 == 2):
    for i in range(0,int(m/2),2):
        b=a[i]*a[m-1-i]
        c=a[i+1]*a[m-2-i]
    b=b/a[int(m/2) + 2]
    c=c*a[int(m/2) + 2]
elif(m % 4 == 3):
    for i in range(0,int(m/2),2):
        b=a[i]*a[m-1-i]
        c=a[i+1]*a[m-2-i]
    c=c/a[int(m/2) + 3]
print (b+c-2)

Submission status: Wrong Answer

Solution code:
import math
""" return a list of the prime factors for a nutural numbers"""
def prime_factorization(k):
  if k < 2:
    return []
  r = math.ceil(math.sqrt(k))
  ans = []
  i = 2
  while i <= r:
    if k % i == 0:
      ans.append(i)
      k //= i
      if k == 1:
          break
    else:
      i += 1
  if k > 1:
    ans.append(k)
    return(k,ans) 
  return (0,ans)

if __name__ == "__main__":
    n = int(input())
    prime_n = prime_factorization(n)
    if prime_n[0] != 0:
        print(int(prime_n[0]+n/prime_n[0] -2))
        exit(0)
    else:
        root_n  = math.ceil(math.sqrt(n))
        for i in range(root_n,n,1):
            if n % i == 0:
                print(int(i+n//i-2))
                exit(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
pf = prime_factorize(N)
pf.sort(reverse=True)

A = 1
B = 1
for i in pf:
  if A <= B:
    A *= i
  else:
    B *= i

ans = A + B - 2

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
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)
print(a)
m=len(a)
print(m)

b=1
c=1

if(m == 1):
    b=a[0]
elif(m == 2):
    b=a[0]
    c=a[1]
elif(m == 3):
    b=a[0]*a[2]
    c=a[1]
elif(m == 4):
    b=a[0]*a[3]
    c=a[1]*a[2]
elif(m == 5):
    b=a[0]*a[4]
    c=a[1]*a[2]*a[3]
elif(m == 6):
    b=a[0]*a[5]*a[2]
    c=a[1]*a[4]*a[3]
elif(m == 7):
    b=a[0]*a[6]*a[2]*a[4]
    c=a[1]*a[6]*a[3]
# 2 2 2 2 3 5 =240
elif(m % 4 == 0):
    for i in range(0,int(m/2),2):
        b=a[i]*a[m-1-i]
        c=a[i+1]*a[m-2-i]
elif(m % 4 == 1):
    for i in range(0,int(m/2),2):
        b=a[i]*a[m-1-i]
        c=a[i+1]*a[m-2-i]
    c=c*a[int(m/2) + 1]
elif(m % 4 == 2):
    for i in range(0,int(m/2),2):
        b=a[i]*a[m-1-i]
        c=a[i+1]*a[m-2-i]
    b=b/a[int(m/2) + 2]
    c=c*a[int(m/2) + 2]
elif(m % 4 == 3):
    for i in range(0,int(m/2),2):
        b=a[i]*a[m-1-i]
        c=a[i+1]*a[m-2-i]
    c=c/a[int(m/2) + 3]
print (b+c-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)
res = float('inf')
for x in a:
    t = int(N/x)
    res = min(res, x+t)
print(res-2)

Submission status: Wrong Answer

Solution code:
n = int(input())

li = [0 for i in range(50)]
x = 2
y = 0
while n >= x and x <= 10**6:
    if n % x == 0:
        n //= x
        li[y] = x
        y += 1
    else:
        x += 1

li.sort(reverse=True)
pair=[1,1]
if li[0]!=0:
    for i in range(50):
        if li[i]!=0:
            if pair[0]<=pair[1]:
                pair[0]*=li[i]
            else:
                pair[1]*=li[i]
    print(sum(pair)-2)
else:
    print(n-1)

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 f2(n):
    N = n
    a = []
    tmpN = n
    while n % 2 == 0:
        # a.append(2)
        tmpN //= 2
        a.append([abs(N//2-2), N//2, 2])
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
        #     a.append(f)
            tmpN//=f
            a.append([abs(N//f-f), N//f, f])
            n //= f
        else:
            f += 2
    if n != 1:
        # a.append(n)

        tmpN //= n
        # print("---------")
        # print("0:"+str(abs(tmpN-n)))
        # print("1:"+str(tmpN))
        # print("2:"+str(n))
        a.append([N-n, N, n])
    return a

n = int(input())
# print(prime_factorize(n))

ans = f2(n)
ans.sort()
# print(ans)
if len(ans) == 1:
        print(n-1)
for i in range(len(ans)):
        if ans[i][1]*ans[i][2] == n:
                print(ans[i][1] + ans[i][2] - 2)
                exit()

Submission status: Wrong Answer

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

for i in range(N):
  j = i + 1
  if N % j == 0:
    if a > j + N / j:
      a = j + N / j
print(a - 2)

Submission status: Wrong Answer

Solution code:
N = int(input())

tmp = [(i,N//i) for i in range(1,50000000) if N % i == 0]

res = 100000000000
for i, x in tmp:
    Min =  (i-1) + (x-1)
    if res > Min:
        res = Min

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())

print(N)
o = []
for i in range(1, N):
  q = N // i
  mod = N % i
  if mod==0:
    d = (i-1) + (q-1)
    o.append(d)


print(min(o))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = 0
ans = 10000000000000000
s = 0
if N%2==0:
    for x in range(1,1000001):
        s=N//x
        if N%x==0:
            a = (s-1)+(x-1)
            if ans>a:
                ans = a
print(ans)

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)
    # print(l)
    l.sort()

    a = 1
    b = 1

    for i in range(len(l)):
        if a <= b:
            a *= l[i]
        else:
            b *= l[i]
    print(a, b)
    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())

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 prod(n):
  result = 1
  for x in n:
    result *= x
  return result
  
a = prime_factorize(n)
b = [a.pop(-1)]

while prod(a) > prod(b):
  prev_result = prod(a) + prod(b)
  b.append(a.pop(0))

try:
  if prev_result < prod(a) + prod(b):
    a.append(b.pop(-1))
except:
  pass
print(prod(a)-1 +prod(b)-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
import sys
sys.setrecursionlimit(1000000)
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)
list1.reverse()
a,b = 1,1
for i in range(len(list1)):
	if a*list1[i] < b*list1[i]:
		a *= list1[i]
	else:
		b *= list1[i]
	

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

Submission status: Wrong Answer

Solution code:
n = int(input())

ans = 0
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)

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

Submission status: Wrong Answer

Solution code:
import math
""" return a list of the prime factors for a nutural numbers"""
def prime_factorization(k):
  if k < 2:
    return []
  r = math.ceil(math.sqrt(k))
  ans = []
  i = 2
  while i <= r:
    if k % i == 0:
      ans.append(i)
      k //= i
      if k == 1:
          break
    else:
      i += 1
  if k > 1:
    ans.append(k)
    return(k,ans) 
  return (0,ans)

if __name__ == "__main__":
    n = int(input())
    prime_n = prime_factorization(n)
    if prime_n[0] != 0:
        print((prime_n[0]-1)+n/prime_n[0] -1)
        exit
    else:
        root_n  = math.ceil(math.sqrt(n))
        for i in range(root_n,n,1):
            if n % i == 0:
                print(int(i+n//i-2))
                exit(0)
    #約数のソートをしたい

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

input_num = int(input())
factors = prime_factorize(input_num)

if len(factors) == 1:
    print(input_num - 1)
elif len(factors) > 2:
    pre = 1
    for i in range(0, len(factors) - 1):
        pre *= factors[i]
    print(pre + factors[-1] - 2)
    
else:
    print(factors[0] - 1 + factors[1] - 1)

Submission status: Wrong Answer

Solution code:
a = int(input())

import itertools
import numpy

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

if len(b)==1:
    print(int(b[0]-1))
elif len(b)==2:
    print(int(b[0]+b[1]-2))
# else:
#     r = b[-1]
#     s = b[-2]
#     for j in range(2,len(b)):
#         i = -1-j
#         if r>s:
#             s = s*b[i]
#         else:
#             r = r * b[i]
#     print(int(r+s-2))

else:
    pr = n
    for i in range(1,(len(b)+1)//2):
        for j in list(itertools.combinations(b,i)):
            if pr > numpy.prod(j)+n/numpy.prod(j)-2:
                pr = numpy.prod(j)+n/numpy.prod(j)-2
    print(int(pr))

Submission status: Wrong Answer

Solution code:
import collections
import heapq as hq
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 = collections.Counter(prime_factorize(N))
B = []
hq.heapify(B)
for i,j in A.items():
    while j != 0:
        hq.heappush(B,i)
        j -= 1
leng = len(B)
if leng == 1:
    print(B[0]-1)
    exit()

ans = []
for i in range(1<<leng):
    a = 1
    b = 1
    for j in range(leng):
        if i>>j == 1:
            a *= B[j]
        else:
            b *= B[j]
    ans.append(a+b)
print(min(ans)-2)

Submission status: Wrong Answer

Solution code:
def soinsu(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
soinsu_list = sorted(soinsu(int(input())))
result = [1, 1]
for s in soinsu_list:
    if result[0] <= result[1]:
        result[0] *= s
    else:
        result[1] *= s
print(result[0] - 1 + result[1] - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = 0
ans = 10000000000000000
s = 0
if N%2==0:
    for x in range(1,2**6*5**6):
        s=N//x
        if N%x==0:
            a = (s-1)+(x-1)
            if ans>a:
                ans = a
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())

kakezan = []
for i in range(N//2, 0, -1):
    if N % i == 0:
        a = i
        b = N/i
        c = a+b
        kakezan.append([a, b, c])
kakezan.sort(key=itemgetter(2)) #リスト1は2次元以の配列

A, B, C = kakezan[0]

print(C-2)

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)
    # print(l)
    l.sort()

    a = 1
    b = 1

    for i in range(len(l)):
        if a <= b:
            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:
#!/usr/bin/env python3
import sys
import numpy as np


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 solve(N: int):

    fct_list = prime_factorize(N)

    result = 1e12

    if len(fct_list) == 2:
        x = fct_list[0]
        y = fct_list[1]
        print(x - 1 + y - 1)
    elif len(fct_list) == 1:
        x = fct_list[0]
        y = 1
        print(x - 1 + y - 1)
    elif len(fct_list) == 0:
        print(0)

    else:
        for i in range(1, len(fct_list) - 1):

            x = np.prod(fct_list[: i + 1])
            y = np.prod(fct_list[i + 1 :])

            result = min(result, x - 1 + y - 1)
        print(result)
    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())

factor = []

tmp = int(N**0.5) + 1
for num in range(2,tmp):
    while N % num == 0:
        N //= num
        factor.append(num)

factor.append(N)
l = sorted(factor)

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)

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
a=int(input())
divisors=make_divisors(a)
divisors.sort()
b=len(divisors)
if b%2==0:
  c = (divisors[int(b/2-0.5)]-1)+(divisors[int(b/2+0.5)]-1)
else:
  c = 2*(divisors[int(b/2)]-1)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
q = 1
w = 1
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 = len(prime_factorize(N))/2
a = prime_factorize(N)
for i in range(math.ceil(A)):
  Q = a[i-1]
  q *= a[i]
for i in range(math.ceil(A)-1):
  W = a[-i]
  w *= a[-i - 1]
  
if len(a) == 2:
  q = a[0]
  w = a[1]
print((q-1) + (w-1))

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 = 1
b = 1
arr = prime_factorize(n)
for i in arr:
    if a <= b:
        a *= i
    else:
        b *= i
print(a+b-2)

Submission status: Wrong Answer

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

def mk_factor(num):
    factor = 2
    factor_list = []

    while num > 1 and factor < int(math.sqrt(num)):
        if num % factor == 0:
            factor_list.append(factor)
            num //= factor
        else:
            factor += 1
        if factor_list == []:
            factor_list.append(num)
    return factor_list

def nearest_path(factor_list):
    if len(factor_list) == 1:
        return [0, factor_list[0]-1]
    else:
        half = len(factor_list) // 2 +1

        move_i_list = factor_list[:half]
        move_i = 1
        for i in move_i_list:
            move_i *= i

        move_j_list = factor_list[half:]
        move_j = 1
        for j in move_j_list:
            move_j *= j

    return [move_i -1, move_j -1]

factor_list = mk_factor(num)
print(sum(nearest_path(factor_list)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#
# Author:   bebebe
# Created:  2019-10-27
#

import math

def divisor(M):
    maxX = int(math.sqrt(M))
    for x in range(2, maxX + 1):
        if M % x == 0:
            return x, M // x
    return 1, M



N = int(input().strip())
N_sqrt = int(math.sqrt(N))


M = N
divi_list = []

while True:
    d1, d2 = divisor(M)
    if d1 == 1:
        divi_list.append(d2)
        break
    else:
        divi_list.append(d1)
        M = d2

a = 1
b = 1
for x in divi_list[::-1]:
    if a < b:
        a *= x
    else:
        b *= x

print(a + b - 2)

Submission status: Wrong Answer

Solution code:
N = int(input())
import numpy as np
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
if is_prime(N):
  print(N-1)
else:
  a = np.floor(np.sqrt(N))
  while True:
    if N%a==0:
      break
    a=a-1
  b=N/a
  print(int(a+b-2))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
# def f(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 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 f2(n):
    N = n
    a = []
    tmpN = n
    while n % 2 == 0:
        # a.append(2)
        tmpN //= 2
        a.append([abs(N//2-2), n//2, 2])
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
        #     a.append(f)
            tmpN//=f
            a.append([abs(N//f-f), N//f, f])
            n //= f
        else:
            f += 2
    if n != 1:
        # a.append(n)

        tmpN //= n
        # print("---------")
        # print("0:"+str(abs(tmpN-n)))
        # print("1:"+str(tmpN))
        # print("2:"+str(n))
        a.append([N-n, N, n])
    return a

n = int(input())
# print(prime_factorize(n))

ans = f2(n)
ans.sort()
# print(ans)
for i in range(len(ans)):
        if ans[i][1]*ans[i][2] == n:
                print(ans[i][1] + ans[i][2] - 2)
                exit()
print(n-1)

Submission status: Wrong Answer

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


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 solve(N: int):

    fct_list = prime_factorize(N)

    result = 1e12

    if len(fct_list) == 2:
        x = fct_list[0]
        y = fct_list[1]
        print(x - 1 + y - 1)
    elif len(fct_list) == 1:
        x = fct_list[0]
        y = 1
        print(x - 1 + y - 1)

    else:
        for i in range(1, len(fct_list) - 1):

            x = np.prod(fct_list[: i + 1])
            y = np.prod(fct_list[i + 1 :])

            result = min(result, x - 1 + y - 1)
        print(result)
    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())

if n == 1:
    print(0)
    exit()
if n ** (0.5) == int(n ** (0.5)):
    print(int(n ** (0.5) * 2 - 2))
    exit()

res = []
x = n
y = 2
while y*y <= x:
    while x % y == 0:
        res.append(y)
        x //= y
    y += 1
if x > 1:
    res.append(x)

if len(res) == 1:
    print(sum(res) - 1)
    exit()

while len(res) != 2:
    res.sort(reverse=True)
    res.append(res.pop(-1) * res.pop(-1))
print(sum(res) - 2)

Submission status: Wrong Answer

Solution code:
n = int(input())

# [[素因数,数]]を出力
def fctr1(n):
    f = []
    c = 0
    r = int(n ** 0.5)
    for i in range(2, r + 2):
        while n % i == 0:
            c += 1
            n = n // i
        if c != 0:
            f.append([i, c])
            c = 0
    if n != 1:
        f.append([n, 1])
    return f


# fact = factorization(n)
fact = fctr1(n)
# fact.sort()

# max_y = fact[-1][0]
# max_y = fact[-1][0] ** fact[-1][1]
# ans = max_y + n // max_y - 2

ans = 10 ** 12 + 1000

for i in range(len(fact)):
    for j in range(fact[i][1]):
        temp = fact[i][0] ** (j + 1)
        temp = temp + n // temp - 2
        ans = min(ans, temp)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
import numpy as np
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
if is_prime(N):
  print(10000000019-1)
else:
  a = np.floor(np.sqrt(N))
  while True:
    if N%a==0:
      break
    a=a-1
  b=N/a
  print(int(a+b-2))

Submission status: Wrong Answer

Solution code:
N = int(input())

tmp = []
for i in range(1,10000000):
    if N % i == 0:
        tmp.append((i, N//i))

res = 100000000000
for i, x in tmp:
    Min =  (i-1) + (x-1)
    if res > Min:
        res = Min

print(res)

Submission status: Wrong Answer

Solution code:
import math


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
      

N = int(input())
nums = list(set(trial_division(N)))
print(min(n + int(N/n) for n in nums)-2)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
mins = N
for i in range(1,math.ceil(math.sqrt(N)) ):
    b = N//i
    a = i
    if a*b == N:
        mins = min(mins,a+b-2)

print(mins)