def divides(n,d):
    '''True if remainder of n/d is 0, False otherwise'''
    return n%d == 0

def least_divisor_from(n,k):
    '''smallest number starting from k, k <= n, that divides n'''
    if divides(n,k):return k
    else: return least_divisor_from(n,k+1)

def least_divisor(n):
    '''smallest divisor of n that is greater than 1'''
    return least_divisor_from(n,2)

def is_prime(n):
    '''True if n is prime, False otherwise'''
    return least_divisor(n)== n

def next_prime(n):
    '''next prime > n'''
    if is_prime(n+1): return n+1
    else: return next_prime(n+1)


def primes_between(a,b):
    '''list of primes in [a..b]'''
    if a>b: return []
    if is_prime(a): return [a]+primes_between(next_prime(a),b)
    else:  return primes_between(next_prime(a),b)

def prime_factors(n):
    '''list of prime factors of n'''

def factorial(n):
    '''returns n*(n-1)*(n-2)*...*2*1'''
    if n==0:return 1
    else:return n* factorial(n-1)

def P(n,r):
    '''returns nPr'''
    if r == 0: return 1
    else: return n*P(n-1,r-1)

def C(n,r):
    '''returns nCr'''
    return P(n,r)//factorial(r)

def gcf(a,b):
    '''greatest common factor of a and b'''
    if a==b: return a
    if a<b: return gcf(a,b-a)
    if a>b: return gcf(a-b,b)

def lcm(a,b):
    '''least common multiple of a and b'''
    return a*b//gcf(a,b

def arithmetic(a,d,n):
    '''arithmetic sequence of n terms'''
    if n == 0: return []
    else: return [a]+arithmetic(a+d,d,n-1)

def geometric(g,r,n):
    '''geometric sequence of n terms'''
    if n==0: return []
    else: return [g]+geometric(g*r,r,n-1)

def first(L):
    '''first item in list L'''
    return L[0]

def rest(L):
    '''all items in list L after the first'''
    return L[1:]

def last(L):
    '''last item in list L'''
    return rest(L)

def init(L):
    '''all items in lst before the last'''

def length(L):
    '''number of items in list L'''
    if L == []: return 0
    else: return 1+length(rest(L))

def sum(L):
    '''sum of items in list L'''

def product(L):
    '''product of items in list L'''

def mean(L):
    '''arithmetic average of list L'''

def smaller(a,b):
    '''smaller of values a and b'''

def min(L):
    '''minimum value in lst'''

def larger(a,b):
    '''larger of values a and b'''

def max(L):
    '''maximum value in list L'''

def remove(item, L):
    '''list L without item'''

def sorted(L):
    '''items of list L sorted in increasing order'''