import random


def is_prime_prob(n, k=5):
    """
    Returns <True> if <n> is a prime number, returns <False> otherwise. It
    uses a probabilistic method based on the Fermat little theorem. The
    probability of false positives can be reduced incresing <k>.

    - The probability of error when returns <True> is zero.
    - The probability of error when returns <False> is 2^-k.
    """
    def power(a, n, p):
        """
        Returns (a ^ n) % p using an iterative procedure to avoid overflow
        for large values of <n>.
        """
        res = 1
        a = a % p

        while (n > 0):

            if (n % 2):                 # If n is odd
                res = (res * a) % p
                n = n - 1

            else:                       # If n is even
                a = (a ** 2) % p
                n = n // 2

        return res % p

    # Corner cases
    if (n == 1 or n == 4):              # Not a prime number
        return False
    if (n == 2 or n == 3):              # Prime number
        return True

    # Repeat k-times for n > 4 and use Fermat little theorem to check if
    # it is NOT a prime number
    for i in range(k):
        a = random.randint(2, n-2)
        if (power(a, n-1, n) != 1):
            return False                # Not a prime number

    return True