z6.3.cpp

#include <iostream>
#include "string.h"
#include "array.h"
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;
}

// Возвращает F(n)=2^(2^n)+1 или 0, если переполнение
unsigned long long fermatNumber(int n)
{
    if (n >= 64) return 0;
    unsigned long long exp = 1ULL << n; // 2^n
    if (exp >= 64) return 0; // переполнение
    unsigned long long val = 1ULL << exp; // 2^(2^n)
    if (val == 0) return 0;
    return val + 1;
}

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

    // Сохраним числа Ферма в Array<unsigned long long>
    Array<unsigned long long> fermas;
    for (int i = 0; i < N; i++)
    {
        unsigned long long f = fermatNumber(i);
        fermas.append(f);
    }

    // Выведем каждое, используя String для формирования сообщения
    for (int i = 0; i < N; i++)
    {
        unsigned long long f = fermas[i];
        String msg = "F(";
        msg = msg + to_string(i).c_str();
        msg = msg + ") = ";

        if (f == 0)
        {
            msg = msg + "OVERFLOW_64_BIT";
        }
        else
        {
            msg = msg + to_string(f).c_str();
            // Простота
            if (isPrime(f))
                msg = msg + " (простое)";
            else
                msg = msg + " (непростое)";
        }

        cout << msg << endl;
    }

    return 0;
}