Problem:


Score : 400 points

Problem Statement

You are given integers N and M.

Consider a sequence a of length N consisting of positive integers such that a_1 + a_2 + ... + a_N = M. Find the maximum possible value of the greatest common divisor of a_1, a_2, ..., a_N.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

N \leq M \leq 10^9

Input

Input is given from Standard Input in the following format:

N M

Output

Print the maximum possible value of the greatest common divisor of a sequence a_1, a_2, ..., a_N that satisfies the condition.

Sample Input 1

3 14

Sample Output 1

2

Consider the sequence (a_1, a_2, a_3) = (2, 4, 8). Their greatest common divisor is 2, and this is the maximum value.

Sample Input 2

10 123

Sample Output 2

3

Sample Input 3

100000 1000000000

Sample Output 3

10000



Sample input:
3 14


Sample output:
2

Submission status: Runtime Error

Solution code:
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 divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

ans_list = []
m,n = map(int, input().split())
fct = factorize(n)
for div in divisorize(fct):
    ans_list.append(num(div))
ans_list.sort()
for number in ans_list:
    if number <= (n//m):
        ans = number
print(ans)

Submission status: Runtime Error

Solution code:
import math
n,m =map(int,input().split())
a = int(m/n)
b = m%n
print(math.gcd(a,b))

Submission status: Runtime Error

Solution code:
from sys import stdin
n,m = int(stdin.readline().split())
ans = 1
x = 1
a = []
while x * x <=m:
 if m%x==0:
  a.append(x)
  a.append(m/x)
 x+=1
for i in a:
 if m/i <= n:
  ans = max(ans,i)
print ans