using System;

internal class Program
{
    static bool IsPrime(int n)
    {
        if (n <= 3)
        {
            return true;
        }
        if (n % 2 == 0 || n % 3 == 0) 
        {
            return false; 
        }
        for (int i = 5; i * i <= n; i += 6)
        {
            if (n % i == 0 || n % (i + 2) == 0) 
            {
                return false;
            }       
        }
        return true;
    }
    static void PrintAllQPow2p1PrimeNumbers(int n)
    {
        for (int i = 2; i<=n; i++)
        {
            if (IsPrime(i))
            {
                if (Math.Sqrt(i-1)%1==0) { Console.WriteLine(i); }
            }
        }
    }

    static void PrintAllFibonacciPrimeNumbers(int n)
    {
        int i = 1;
        int i_prv = 1;
        for(int i_crnt = 2;i_crnt<=n; i_crnt=i_prv+i)
        {
            i = i_prv;
            i_prv = i_crnt;
            if (IsPrime(i_crnt)) { Console.WriteLine(i_crnt); }
        }
    }

    static void Main()
    {
        Console.Write("Введіть крайню межу для діапазону [2,n]:");
        int n = int.Parse(Console.ReadLine());

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

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