#include <cstdlib>
#include <cmath>
#include <iostream>
 
using namespace std;
 
uint64_t isqrt( uint64_t const n )
{
    double x = n >> (__builtin_clzll(n)/2); // x ist höchstens 2^32
    double old_x;
    for(;;)
    {
        old_x = x;
        x = (x + n/x)/2;
 
        if( std::abs(x - old_x) < 1 )
            break;
    }
 
    return x;
}
 
int main()
{
    for ( uint64_t i = 2; i < 3000000; ++i )
    {
        if ( ( i & ( i - 1 ) ) == 0 )
            cout << i << '\n';
        uint64_t square = i * i;
        if ( isqrt( square - 1 ) != i - 1 )
            cout << "error: " << i << " ^2 - 1\n";
        if ( isqrt( square ) != i )
            cout << "error: " << i << " ^2\n";
        if ( isqrt( square + 1 ) != i )
            cout << "error: " << i << " ^2 + 1\n";
    }
}