using System;

class Program
{
   
    static bool IsPrime(long number)
    {
        if (number < 2)
        {
            return false;
        }

        for (long i = 2; i * i <= number; i++)
        {
            if (number % i == 0)
            {
                return false;
            }
        }

        return true;
    }

   
    static void PrintAllQPow2p1PrimeNumbers(int n)
    {
        long q = 1;
        long number = q * q + 1;

        while (number <= n)
        {
            if (IsPrime(number))
            {
                Console.Write(number + " ");
            }

            q++;
            number = q * q + 1;
        }

        Console.WriteLine();
    }

    
    static void PrintAllFibonacciPrimeNumbers(int n)
    {
        long first = 1;
        long second = 1;

        while (second <= n)
        {
            if (IsPrime(second))
            {
                Console.Write(second + " ");
            }

            long third = first + second;
            first = second;
            second = third;
        }

        Console.WriteLine();
    }

    static void Main()
    {
        Console.Write("Введіть n: ");
        int n = Convert.ToInt32(Console.ReadLine());

        Console.WriteLine("Прості числа вигляду q^2 + 1:");
        PrintAllQPow2p1PrimeNumbers(n);

        Console.WriteLine("Прості числа Фібоначчі:");
        PrintAllFibonacciPrimeNumbers(n);
    }
}