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

Submission attempts (in order):
n,m=(int(i) for i in input().split(' '))
i=m
if m=2147483647:
  print(1)
  exit()
while True:
  if i==1:
    print(i)
    break
  if m%i==0 and m//i>=n:
    print(i)
    break
  else:
    i-=1


import random

def is_prime(q,k=10):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
for i in range(1,n):
  if m%i==0 and is_prime(m//i) and (i==1 or m//i>n):
    print('1')
    exit()
for i in range(1,m):
  if i==m:
    print(1)
    break
  if m%i==0 and i>=n:
    print(m//i)
    break


n,m=(int(i) for i in input().split(' '))
i=m//i
while True:
  if m%i==0 and m//i>=n:
    print(i)
    break
  else:
    i-=1

n,m=(int(i) for i in input().split(' '))
for i in range(1,m//n+1):
  if i==m:
    print(1)
    break
  if m%i==0 and i>=n:
    print(m//i)
    break

import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
if n<1000:
  for i in range(1,n):
    if m%i==0 and (is_prime(i) or i=1) and is_prime(m//i) and (i==1 or m//i<n):
      print('1')
      exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break
  if m-i-n>0 and m%(m-i-n)==0 and m//(m-i-n)>n:
    print(m-i-n)
    break


def divisor(m,k):
  divisor=[]
  for i in range(1,k+1):
    if m%i==0:
      divisor.append(i)
  return divisor

n,m=(int(i) for i in input().split(' '))
print(divisor(m,m//n))
for i in divisor(m)[::-1]:
  if i==1:
    break
  if m%i==0 and m//i>=n:
    print(i)
    break


def factor(x){
  factor=[]
  if x==1:
    return
  else:
  i=2
    while x>1:
      if x%i==0:
        factor.append([i,1])
        x/=i
        while x%i==0:
          factor[-1][1]+=1
          x/=i
      i+=1
    return factor

n,m=(int(i) for i in input().split(' '))
factor=factor(m)
ans=1
for data in factor:
  data[1]=data[1]/n
  ans=ans*(data[0]**data[1])
print(ans)


import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))

if n==1:
  print(m)
  exit()
if True:
  for i in range(1,n):
    if m%i==0 and is_prime(m//i) and m//i>n:
      print('1')
      exit()
for i in range(1,m//n+1)[::-1]:
  if i==1:
    print(i)
    break
  if m%i==0 and m//i>=n:
    print(i)
    break


n,m=(int(i) for i in input().split(' '))
print(n)

n,m=(int(i) for i in input().split(' '))
for i in range(1,m//n):
  if i==1:
    print(i)
    break
  if m%i==0 and m//i>=n:
    print(i)
    break

import random

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 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 t & 1 == 0:
            return False

    return True

n,m=(int(i) for i in input().split(' '))
for i in range(1,n)
  if m%i==0 and is_prime(m//i):
    print('1')
    exit()
for i in range(1,m//n+1)[::-1]:
  if i==1:
    print(i)
    break
    if m%i==0 and m//i>=n:
      print(i)
      break


print(n)

def divisor(m):
  divisor=[]
  for i in range(2,m//2+1):
    if m%i==0:
      divisor.append(i)
  divisor=[1]+divisor+[m]
  return divisor

n,m=(int(i) for i in input().split(' '))
print(divisor(m))
for i in divisor(m)[::-1]:
  if i==1:
    break
  if m%i==0 and m//i>=n:
    print(i)
    break


n,m=(int(i) for i in input().split(' '))
for i in range(1,1000)[::-1]:
  if i==1:
    print(i)
    break
  if m%i==0 and m//i>=n:
    print(m//i)
    break


import random

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 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 t & 1 == 0:
            return False

    return True

n,m=(int(i) for i in input().split(' '))
for i in range(1,n):
  if m%i==0 and is_prime(m//i):
    print('1')
    exit()
for i in range(1,m//n+1)[::-1]:
  if i==1:
    print(i)
    break
  if m%i==0 and m//i>=n:
    print(i)
    break


import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
if m%n>10000:
  for i in range(1,n):
    if m%i==0 and is_prime(i) and is_prime(m//i) and (i==1 or m//i<n):
      print('1')
      exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break
  if m%(m-i+1)==0
    print(m-i+1)
    break


import math
import random

def is_prime(n):
    if n == 1: return False
    if n == 2: return True

    for k in range(100):
        a = random.randint(2, n - 1)

        if gcd(n, a) != 1:
            return False

        if pow(a, n - 1, n) != 1:
            return False

    return True

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

if __name__ == '__main__':
    print(is_prime(2 ** 89 - 1))


n,m=(int(i) for i in input().split(' '))
if is_prime(m):
  print('1')
else:
  for i in range(1,m//n+1)[::-1]:
    if i==1:
      print(i)
      break
    if m%i==0 and m//i>=n:
      print(i)
      break


def factor(x):
  factor=[]
  if x==1:
    return
  else:
    i=2
    while x>1:
      if x%i==0:
        factor.append([i,1])
        x/=i
        while x%i==0:
          factor[-1][1]+=1
          x/=i
      i+=1
    return factor

n,m=(int(i) for i in input().split(' '))
factor=factor(m)
ans=1
for data in factor:
  data[1]=data[1]//n
  ans=ans*(data[0]**data[1])
print(ans)


import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
for i in range(1,n):
  if m%i==0 and (is_prime(i) or i==1) and is_prime(m//i) and (i==1 or m//i<n):
    print('1')
    exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Accepted