def main(verbose=False):
    prime_max = 10 ** 5
    PRIMES = sieve(prime_max)
    found = []
    n = 2
    while len(found) < 25:
        n += 1
        if n > prime_max:
            prime_max *= 10
            PRIMES = sieve(prime_max)

        if n % 2 == 0 or n % 5 == 0 or n in PRIMES:
            continue

        basis = n
        if n % 3 == 0:
            basis = 9 * n

        if (n - 1) % order_mod_n(10, basis) == 0:
            found.append(n)
    if verbose:
        return ('%s.\nAs a check, the first five values are calculated to be '
                '%s, as stated.' % (sum(found),
                                    ', '.join(str(num) for num in found[:5])))
    else:
        return sum(found)

def main(verbose=False):
    PRIMES = sieve(10 ** 5)
    running_sum = 0
    for prime in PRIMES:
        if not prime_divides_repunit_power10(prime):
            running_sum += prime
    return running_sum

def main(verbose=False):
    prime_factors_hash = {}

    MINIMUM_SOLUTIONS = 4*(10**6)
    # P^k < 10**7 (10 mil)
    powers = [power_up_to_digits(prime, 7)
              for prime in [3, 5, 7]]
    products = [reduce(operator.mul, triple) for
                triple in list(i_product(*powers))]
    products = [product for product in sorted(products)
                if product > 2*MINIMUM_SOLUTIONS][:20]

    PRIMES = sieve(100)

    max_prod = 10**21
    res = []
    for product in products:
        factors = prime_factors(product, unique=False, hash_=prime_factors_hash)
        factors = [(factor - 1)/2 for factor in factors][::-1]
        curr_prod = 1
        for i, exp in enumerate(factors):
            curr_prod = curr_prod*(PRIMES[i]**exp)

        if curr_prod < max_prod:
            max_prod = curr_prod

    return max_prod

def main(verbose=False):
    # layer/primes
    #     2/3
    #  1581/835
    #  3536/1677
    #  5000/2249
    # 13121/5248, winning layer

    # ratio >= .1 iff 10*(primes/total) >= 1 iff 10*primes >= total
    # iff 10*primes >= 4*index - 3
    FAILURE_POINT = 10 ** 9
    PRIMES = sieve(int(sqrt(FAILURE_POINT)) + 1)

    layer = 2
    num_primes = 3
    while 10 * num_primes >= 4 * layer - 3:
        layer += 1
        candidates = [(2 * layer - 1) ** 2 - 2 * (layer - 1) * i
                      for i in range(1, 4)]
        if candidates[-1] >= FAILURE_POINT:
            raise ValueError("Sieve was not big enough, restart function")
        for candidate in candidates:
            if is_prime(candidate, primes=PRIMES, failure_point=FAILURE_POINT):
                num_primes += 1
    side_length = 2 * layer - 1  # 2*(layer - 1) + 1
    return side_length

def main(verbose=False):
    PRIMES = sieve(10 ** 7)
    running_sum = 0
    for prime in PRIMES:
        if prime not in [2, 5]:
            running_sum += inverse_mod_n(10, prime)
    return running_sum

def main(verbose=False):
    primes = sieve(100)

    MAX_n = 10 ** 16

    product_factor_pairs = [(1, 0)]
    product_hash = {0: [1]}
    for num_factors in range(1, 13 + 1):
        product_hash[num_factors] = []

    # (1,0) becomes
    # (1,0), (p, 1) becomes
    # (1,0), (p, 1), (q,1), (q*p, 2) etc.
    for prime in primes:
        to_add = []
        for product, num_factors in product_factor_pairs:
            if prime * product < MAX_n:
                to_add.append((prime * product, num_factors + 1))
                product_hash[num_factors + 1].append(prime * product)
        product_factor_pairs += to_add

    result = 0
    sign = -1
    for num_factors in range(4, 13 + 1):
        sign = -sign
        PIE_factor = sign * choose(num_factors - 1, 3)
        current_sum = 0
        for product in product_hash[num_factors]:
            current_sum += MAX_n / product  # integer division
        result += PIE_factor * current_sum

    return result

def all_circular(n):
    # the number of digits limits the size of all permutations
    digs = len(str(n))
    possible_primes = [2, 5] + \
        [prime for prime in sieve(10**digs - 1)
         if contains_only_digits(prime, [1, 3, 7, 9])]
    return [prime for prime in possible_primes if prime <= n
             and all_circular_perm_in(prime, possible_primes)]

def main(verbose=False):
    # By the prime number theorem, pi(x) =~ x/ln(x)
    # pi(x) >= 10001 when x >= 10001 ln(x)
    # To be safe, we'll double it and solve
    # x = 20002 ln(x)

    # We are left with approximately 248490
    primes = sieve(248490)
    return primes[10001 - 1]

def main(verbose=False):
    # sieve(6000) will do it (answer is 5777)
    curr = 9
    primes = sieve(5777)
    while is_possible(curr, primes):
        curr += 2
        while curr in primes:
            curr += 2
    return curr

def main(verbose=False):
    problem_max = 10 ** 6
    count = 0
    PRIMES = sieve(problem_max)
    max_L = int(round((sqrt(12 * problem_max - 3) - 3) / 6))
    for L in xrange(1, max_L + 1):
        difference = (L + 1) ** 3 - L ** 3
        if difference in PRIMES:
            count += 1
    return count

def prime_sequence_exists(length, digits, primes=[]):
    """
    Returns True if a sequence of length consecutive primes which sums
    to less than 10**digits also sums to a prime number
    """
    cap = 10**digits
    if primes == []:
        primes = sieve(cap)
    sums = [sum(seq) for seq in all_prime_seqs(length, digits, primes)]
    return (set(sums).intersection(primes) != set())

def main(verbose=False):
    problem_max = 10 ** 6
    PRIMES = sieve(problem_max)
    # ignore zero index
    ratios = [(1, index) for index in range(problem_max + 1)]
    for prime in PRIMES:
        ratios[prime::prime] = [((ratio * prime * 1.0) / (prime - 1), index)
                                for ratio, index in ratios[prime::prime]]
    ratios.sort(key=lambda pair: pair[0], reverse=True)
    return ratios[0][1]

def matches(problem_max):
    PRIMES = sieve(problem_max)
    phi_list = range(problem_max + 1)  # ignore zero index
    for prime in PRIMES:
        phi_list[prime::prime] = [(val / prime) * (prime - 1) for val in
                                  phi_list[prime::prime]]
    cands = [(val, phi_list[val]) for val in range(2, problem_max + 1)
             if same_digits(val, phi_list[val])]
    cands.sort(key=lambda cand: (cand[0] * 1.0) / cand[1])
    return cands[0][0]

def main(verbose=False):
    PRIMES = sieve(10 ** 6)
    prime_index = 3  # p0=2, p1=3, and p2=5 are false positives
    matches = []
    while len(matches) < 40:
        prime = PRIMES[prime_index]
        if prime_divides_repunit_power10(prime, 9):
            matches.append(prime)
        prime_index += 1

    return sum(matches)

def main(verbose=False):
    # Since p_n > 70710, to be safe let's multiply by 10
    PRIMES = sieve(707100)
    # The odd primes are the even indices here
    prime_index = 1
    product = 2*(1*2) # p_1 = 2
    while product < 10**10:
        prime_index += 2
        prime = PRIMES[prime_index-1]
        product = 2*(prime_index*prime)
    return prime_index

def all_radicals(n):
    PRIMES = sieve(n)
    result = {1: 1}
    for i in range(2, n + 1):
        if i in PRIMES:
            result[i] = i
        prime, quotient = first_prime_divisor(i, PRIMES)
        if quotient % prime == 0:
            result[i] = result[quotient]
        else:
            result[i] = result[quotient]*prime
    return result

def main(verbose=False):
    PRIMES = sieve(10 ** 6 + 3)  # 10**6 + 3 is the final value of p_2

    running_sum = 0
    for index in range(2, len(PRIMES) - 1):
        p_1 = PRIMES[index]
        p_2 = PRIMES[index + 1]
        ten_inverse = inverse_mod_n(10, p_2)
        digits = len(str(p_1))
        k = (ten_inverse ** digits) * (p_2 - p_1) % p_2
        running_sum += int('%s%s' % (k, p_1))
    return running_sum

def longest_prime_sequence(digits, primes=[]):
    """
    Returns the length of the most consecutive primes which sum
    to a prime and sum to less then 10**digits
    """
    if primes == []:
        primes = sieve(10**digits)
    max_length = max_prime_length(digits, primes)
    for length in range(max_length, 0, -1):
        if prime_sequence_exists(length, digits, primes):
            return length
    raise ValueError("Algorithm failed")

def main(verbose=False):
    MAX_n = 10 ** 6 - 1
    distinct_solutions = 10
    PRIMES = sieve(int(sqrt(MAX_n)) + 1)
    factor_hash = {}

    count = 0
    for n in range(1, MAX_n + 1):
        factor_list = factors(n, factor_hash, PRIMES)
        if len(num_solutions(factor_list)) == distinct_solutions:
            count += 1
    return count

def main(verbose=False):
    MAX_n = 987654321
    PRIMES = sieve(int(sqrt(MAX_n)))
    # A 9 digit pandigital will have digit sum 45, so can't be prime
    # must be divisible by 9
    for i in range(8, 1, -1):
        cand = [str(dig) for dig in range(1, i + 1)]
        cand = int("".join(cand))
        candidates = sorted(all_permutations_digits(cand))[::-1]
        for candidate in candidates:
            if is_prime(candidate, primes=PRIMES, failure_point=MAX_n):
                return candidate
    raise ValueError("No prime was found, algorithm busted.")