z6.2.cpp

#include <iostream>
using namespace std;

bool isPrime(unsigned long long x)
{
    if (x < 2) return false;
    for (unsigned long long i = 2; i*i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

// Вычисляет 2^(2^n) + 1 в 64-битном диапазоне
// Вернёт 0, если результат выходит за пределы unsigned long long
unsigned long long fermatNumber(int n)
{
    // 2^n
    if (n >= 64)
    {
        // 2^n уже не влезет в 64 бита, значит точно overflow
        return 0;
    }
    unsigned long long exponent = 1ULL << n; // это 2^n

    // Если exponent >= 64, тогда 2^(2^n) точно не влезет
    if (exponent >= 64)
    {
        return 0;
    }
    unsigned long long val = 1ULL << exponent; // 2^(2^n)
    // Проверим, что не было переполнения
    if (val == 0) return 0; // переполнение
    return val + 1ULL;      // F_n
}

int main()
{
    int N;
    cout << "Сколько чисел Ферма вывести (n=0..N-1)? ";
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        unsigned long long f = fermatNumber(i);
        if (f == 0)
        {
            cout << "F(" << i << ") слишком велико для 64-бит.\n";
            continue;
        }
        cout << "F(" << i << ")=" << f;
        if (isPrime(f)) cout << " (простое)\n";
        else            cout << " (непростое)\n";
    }
    return 0;
}