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 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 lucas_test(n):
    prev_n = n - 1
    prime_divisors = get_only_prime_divisors(prev_n)
    for a in range(2, n):
        is_prime = True
        if pow(a, prev_n, n) != 1:
            continue
        for q in prime_divisors:
            if pow(a, prev_n // q, n) == 1:
                is_prime = False
                break
        if is_prime:
            return True
    return False


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


def create_prime(n):
    while True:
        number = get_random_number(n)
        if lucas_test(number):
            return number


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