using System;
class Program
{
static bool IsPrime(long number)
{
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 = 2;
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);
}
}
dXNpbmcgU3lzdGVtOwoKY2xhc3MgUHJvZ3JhbQp7CiAgIAogICAgc3RhdGljIGJvb2wgSXNQcmltZShsb25nIG51bWJlcikKICAgIHsKICAgICAgICAKICAgICAgICBmb3IgKGxvbmcgaSA9IDI7IGkgKiBpIDw9IG51bWJlcjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKG51bWJlciAlIGkgPT0gMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KCiAgIAogICAgc3RhdGljIHZvaWQgUHJpbnRBbGxRUG93MnAxUHJpbWVOdW1iZXJzKGludCBuKQogICAgewogICAgICAgIGxvbmcgcSA9IDE7CiAgICAgICAgbG9uZyBudW1iZXIgPSBxICogcSArIDE7CgogICAgICAgIHdoaWxlIChudW1iZXIgPD0gbikKICAgICAgICB7CiAgICAgICAgICAgIGlmIChJc1ByaW1lKG51bWJlcikpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGUobnVtYmVyICsgIiAiKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcSsrOwogICAgICAgICAgICBudW1iZXIgPSBxICogcSArIDE7CiAgICAgICAgfQoKICAgICAgICBDb25zb2xlLldyaXRlTGluZSgpOwogICAgfQoKICAgIAogICAgc3RhdGljIHZvaWQgUHJpbnRBbGxGaWJvbmFjY2lQcmltZU51bWJlcnMoaW50IG4pCiAgICB7CiAgICAgICAgbG9uZyBmaXJzdCA9IDE7CiAgICAgICAgbG9uZyBzZWNvbmQgPSAyOwoKICAgICAgICB3aGlsZSAoc2Vjb25kIDw9IG4pCiAgICAgICAgewogICAgICAgICAgICBpZiAoSXNQcmltZShzZWNvbmQpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlKHNlY29uZCArICIgIik7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGxvbmcgdGhpcmQgPSBmaXJzdCArIHNlY29uZDsKICAgICAgICAgICAgZmlyc3QgPSBzZWNvbmQ7CiAgICAgICAgICAgIHNlY29uZCA9IHRoaXJkOwogICAgICAgIH0KCiAgICAgICAgQ29uc29sZS5Xcml0ZUxpbmUoKTsKICAgIH0KCiAgICBzdGF0aWMgdm9pZCBNYWluKCkKICAgIHsKICAgICAgICBDb25zb2xlLldyaXRlKCLQktCy0LXQtNGW0YLRjCBuOiAiKTsKICAgICAgICBpbnQgbiA9IENvbnZlcnQuVG9JbnQzMihDb25zb2xlLlJlYWRMaW5lKCkpOwoKICAgICAgICBDb25zb2xlLldyaXRlTGluZSgi0J/RgNC+0YHRgtGWINGH0LjRgdC70LAg0LLQuNCz0LvRj9C00YMgcV4yICsgMToiKTsKICAgICAgICBQcmludEFsbFFQb3cycDFQcmltZU51bWJlcnMobik7CgogICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKCLQn9GA0L7RgdGC0ZYg0YfQuNGB0LvQsCDQpNGW0LHQvtC90LDRh9GH0ZY6Iik7CiAgICAgICAgUHJpbnRBbGxGaWJvbmFjY2lQcmltZU51bWJlcnMobik7CiAgICB9Cn0=