import math

# Programmer: Sriram Pemmaraju
# Date: 3/5/2015

# Boolean function that tests if the given positive integer parameter
# N is a prime. 
def isPrime(N):
    factor = 2 # tracks candidate factors of N
    
    # we only need to consider factors <= sqrt(N)
    factorUpperBound = math.sqrt(N) 

    while (factor <= factorUpperBound):
        if (N % factor == 0):
            return False
        factor = factor + 1
    return True

# Returns a pairs of consecutive primes that are <= N and have the largest
# possible gap among all consecutive primes <= N. The consecutive primes are
# returned as a size-2 list
def farthestConsecutivePrimes(N):
    m = 2 # previous prime
    n = 2 # current prime
    
    # these two variables will remember the consecutive primes with largest gap
    # In the beginning we don't know very much, so we initialize these both to 2
    savedM = 2
    savedN = 2
    
    # Consider each value of n <= N and test n for primality. If n is a prime
    # compare the gap between n and m (the previous prime) versus savedN - savedM
    # which is the largest gap known thus far
    while n <= N:
        if isPrime(n):
            if (n - m) > (savedN - savedM):
                savedN = n
                savedM = m
            m = n # move m to current prime
        n = n + 1   
                
    return [savedM, savedN]