Problem: 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.

Submission attempts (in order):


def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


N=100
# N=int(input())

a=1
b=N//a
dis=abs(a-b)

Li=prime_factorization(N)
# print(Li)

for p in range(2**len(Li)):
    bit=[]
    if a>N**0.5:
        break
    for e in range(len(Li)):
        if (p>>e)&1==1:
            bit.append(1)
        else:
            bit.append(0)
    # print(bit)
        proindex=[]
        for _ in range(len(bit)):
            if bit[_] ==1:
                proindex.append(_)
        _a=1
        for j in range(len(Li)):
            if proindex.count(j)==1:
                _a*=Li[j]
        _b=N//_a
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis
# print(a,b)

print(a-1+b-1)



def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


# N=100
N=int(input())

a=N
b=1
dis=abs(a-b)

Li=prime_factorization(N)
for p in range(2**len(Li)):
    bit=[]
    for e in range(len(Li)):
        if (p>>e)&1==1:
            bit.append(1)
        else:
            bit.append(0)
    # print(bit)
        proindex=[]
        for _ in range(len(bit)):
            if bit[_] ==1:
                proindex.append(_)
        _a=1
        for j in range(len(Li)):
            if proindex.count(j)==1:
                _a*=Li[j]
        _b=N//_a
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b

print(a,b)



def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


# N=100
N=int(input())

a=1
b=N//a
dis=abs(a-b)

Li=prime_factorization(N)
print(Li)

for p in range(2**len(Li)):
    bit=[]
    for e in range(len(Li)):
        if (p>>e)&1==1:
            bit.append(1)
        else:
            bit.append(0)
    # print(bit)
        proindex=[]
        for _ in range(len(bit)):
            if bit[_] ==1:
                proindex.append(_)
        _a=1
        for j in range(len(Li)):
            if proindex.count(j)==1:
                _a*=Li[j]
        _b=N//_a
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis
print(a,b)
print(a-1+b-1)



def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


N=100
# N=int(input())

a=1
b=N//a
dis=abs(a-b)

for i in range(1,int(N**0.5)+1):
    if N%i==0:
        _a=i
        _b=N/i
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis

print(a-1+b-1)

N=int(input())

a=1
b=N//a
dis=abs(a-b)

for i in range(int(N**0.5)+1):
    if N%i==0:
        _a=i
        _b=N/i
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis

print(a-1+b-1)



def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


N=100
# N=int(input())

a=N
b=1
dis=abs(a-b)

Li=prime_factorization(N)
for p in range(2**len(Li)):
    bit=[]
    for e in range(len(Li)):
        if (p>>e)&1==1:
            bit.append(1)
        else:
            bit.append(0)
    # print(bit)
        proindex=[]
        for _ in range(len(bit)):
            if bit[_] ==1:
                proindex.append(_)
        _a=1
        for j in range(len(Li)):
            if proindex.count(j)==1:
                _a*=Li[j]
        _b=N//_a
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b

print(a,b)



def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


N=100
# N=int(input())

a=1
b=N//a
dis=abs(a-b)

Li=prime_factorization(N)
# print(Li)

for p in range(2**len(Li)):
    bit=[]
    for e in range(len(Li)):
        if (p>>e)&1==1:
            bit.append(1)
        else:
            bit.append(0)
    # print(bit)
        proindex=[]
        for _ in range(len(bit)):
            if bit[_] ==1:
                proindex.append(_)
        _a=1
        for j in range(len(Li)):
            if proindex.count(j)==1:
                _a*=Li[j]
        _b=N//_a
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis
        if a<N**0.5 or b<N**0.5:
            break
# print(a,b)

print(a-1+b-1)



def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


# N=100
N=int(input())

a=1
b=N//a
dis=abs(a-b)

Li=prime_factorization(N)
# print(Li)

for p in range(2**len(Li)):
    bit=[]
    for e in range(len(Li)):
        if (p>>e)&1==1:
            bit.append(1)
        else:
            bit.append(0)
    # print(bit)
        proindex=[]
        for _ in range(len(bit)):
            if bit[_] ==1:
                proindex.append(_)
        _a=1
        for j in range(len(Li)**0.5):
            if proindex.count(j)==1:
                _a*=Li[j]
        _b=N//_a
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis
# print(a,b)

print(a-1+b-1)



def prime_factorization(N):
    n=N
    a=2
    prime_factor=[]
    while a**2<=n:
        while n%a==0:
            prime_factor.append(a)
            n//=a
        a+=1
    if n>1:
        prime_factor.append(n)
    return prime_factor


N=int(input())

a=1
b=N//a
dis=abs(a-b)

for i in range(1,int(N**0.5)+1):
    if N%i==0:
        _a=i
        _b=N/i
        _dis=abs(_a-_b)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis

print(a-1+b-1)

N=int(input())

a=1
b=N//a
dis=abs(b-a)

for i in range(1,int(N**0.5)+1):
    if N%i==0:
        _a=i
        _b=N//i
        _dis=abs(_b-_a)
        if _dis<dis:
            a=_a
            b=_b
            dis=_dis

print(a-1+b-1)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Accepted