Вычисление чисел Ферма


Простые числа Ферма описываются формулой x(n)=2^(2^n)+1.

На самом деле уже 6-ое число не является простым, а также все последующие
числа вплоть до n=32 включительно. На данный момент известно только 5 простых
чисел Ферма: 3, 5, 17, 257, 65537. С числа n=6 начинаются вычислительные сложности,
поскольку оно выходит за рамки 64-битных чисел long long int. Для установления факта
простоты чисел Ферма рекомендуется использовать тест Пепина.

#include <iostream>
#include <iomanip>

using namespace std;

bool is_prime(unsigned long long int n) {
    if (n <= 1)
        return false;
 
    for (unsigned long long int j = 2; j * j <= n; j++)
         if (n % j == 0) return false;
 
    return true;
}

unsigned long long int pow(unsigned long long int k, long s)
{
	if (s==0) return 1;
	unsigned long long int res = k;
	for(long i=2;i<=s;i++) res*=k;
	return res;
}

unsigned long long int ferma(int k)
{
	return (unsigned long long int)pow(2,pow(2,k))+1;
}

int main()
{
	int N=5;
	for(int i=0;i<=N;i++)
	{
		unsigned long long int f = ferma(i);
		cout << setw(3) << i;
		cout << setw(20) << f;
		cout << setw(20) << 
                   (is_prime(f)?"PRIME NUM":"COMPOSITE") << endl;
	}
	cout << "sizeof(unsigned long long int): " << 
                sizeof(unsigned long long int) << endl;
	return 1;
}