def square(x): return x * x
def is_even(n):
    return n % 2 == 0
def expmod(base, exp, m):
    return (1 if exp == 0
            else square(expmod(base, exp // 2, m)) % m if is_even(exp)
            else (base * expmod(base, exp - 1, m)) % m)
def random(n):
    return math_floor(random_random() * n)
def fermat_test(n):
    def try_it(a):
        return expmod(a, n, n) == a
    return try_it(1 + math_floor(random_random() * (n - 1)))
def fast_is_prime(n, times):
    return (True if times == 0
            else fast_is_prime(n, times - 1) if fermat_test(n)
            else False)
def timed_prime_test(n):
    print(n)
    return start_prime_test(n, get_time())
def start_prime_test(n, start_time):
    return (report_prime(get_time() - start_time)
            if fast_is_prime(n, math_floor(math_log(n)))
            else True)
def report_prime(elapsed_time):
    print(" *** ")
    print(elapsed_time)

timed_prime_test(10007)
# timed_prime_test(10009)
# timed_prime_test(10037)
# timed_prime_test(100003, 3)
# timed_prime_test(100019, 3)
# timed_prime_test(100043, 3)
# timed_prime_test(1000003, 3)
# timed_prime_test(1000033, 3)
# timed_prime_test(1000037, 3)
