51 lines
1.1 KiB
C++
51 lines
1.1 KiB
C++
#include <cstdint>
|
|
#include <iomanip>
|
|
#include <iostream>
|
|
|
|
bool is_prime(uint64_t n) {
|
|
if (n < 2)
|
|
return false;
|
|
if (n % 2 == 0)
|
|
return n == 2;
|
|
if (n % 3 == 0)
|
|
return n == 3;
|
|
for (uint64_t p = 5; p * p <= n; p += 4) {
|
|
if (n % p == 0)
|
|
return false;
|
|
p += 2;
|
|
if (n % p == 0)
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
class motzkin_generator {
|
|
public:
|
|
uint64_t next();
|
|
private:
|
|
uint64_t n = 0;
|
|
uint64_t m0 = 1;
|
|
uint64_t m1 = 1;
|
|
};
|
|
|
|
uint64_t motzkin_generator::next() {
|
|
uint64_t m = n > 1 ? (m1 * (2 * n + 1) + m0 * (3 * n - 3)) / (n + 2) : 1;
|
|
++n;
|
|
m0 = m1;
|
|
m1 = m;
|
|
return m;
|
|
}
|
|
|
|
int main() {
|
|
std::cout.imbue(std::locale(""));
|
|
std::cout << " n M(n) Prime?\n";
|
|
std::cout << "-----------------------------------\n";
|
|
std::cout << std::boolalpha;
|
|
motzkin_generator mgen;
|
|
for (int i = 0; i < 42; ++i) {
|
|
uint64_t n = mgen.next();
|
|
std::cout << std::setw(2) << i << std::setw(25) << n << " "
|
|
<< is_prime(n) << '\n';
|
|
}
|
|
}
|