import math
import random


def erathosphene(n):
    is_prime = [True] * n
    p = 2
    while p * p < n:
        cur = p * p;
        while cur < n:
            is_prime[cur] = False;
            cur += p;
        while not is_prime[p + 1]:
            p += 1;
        p += 1
    primes = []
    for i, p in enumerate(is_prime):
        if p:
            primes.append(i)
    return primes[2:]


def fast_power(base, power):
    result = 1
    while power > 0:
        if power % 2 == 0:
            power = power // 2
            base *= base
        else:
            power -= 1
            result = result * base
            power = power // 2
            base *= base
    return result


def get_only_prime_divisors(n):
    factors = []
    if (n % 2 == 0):
        factors.append(2)

    while (n % 2 == 0):
        n = n // 2

    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if (n % i == 0):
            factors.append(i)

        while (n % i == 0):
            n = n // i

    if (n > 2):
        factors.append(n)

    return factors


def pocklington_criterion(n, borded_a):
    prev_n = n - 1
    prime_divisors = get_only_prime_divisors(prev_n)
    prime_divisors = filter(lambda q: q > math.sqrt(n) - 1, prime_divisors)

    for a in range(2, borded_a):
        if pow(a, prev_n, n) != 1:
            continue
        for q in prime_divisors:
            if math.gcd(n, fast_power(a, prev_n // q) - 1) == 1:
                return True
    return False


def get_random_number(n):
    while True:
        number = random.randrange(2 ** (n-1) + 1, 2 ** n - 1)
        for divisor in first_primes_list:
            if number % divisor == 0 and divisor ** 2 <= number:
                break
        else:
            return number


def create_prime(n, a):
    while True:
        number = get_random_number(n)
        if pocklington_criterion(number, a):
            return number


first_primes_list = erathosphene(500)
if __name__ == "__main__":
    print("Введите количество бит генерируемого простого числа:")
    n = int(input())
    print("Введите верхнюю границу числа 'a' в критерии Поклингтона (не меньше 3):")
    a = int(input())
    result = create_prime(n, a)
    print(f"Сгенерированное простое число: {result}")