Motzkin numbers: Difference between revisions
Added C++ solution
(→{{header|Fermat}}: -add output) |
(Added C++ solution) |
||
Line 289:
14,996,791,899,280,244,858,336,604
43,881,711,243,248,048,262,611,670 </pre>
=={{header|C++}}==
<lang cpp>#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 ? m = (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';
}
}</lang>
{{out}}
<pre>
n M(n) Prime?
-----------------------------------
0 1 false
1 1 false
2 2 true
3 4 false
4 9 false
5 21 false
6 51 false
7 127 true
8 323 false
9 835 false
10 2,188 false
11 5,798 false
12 15,511 true
13 41,835 false
14 113,634 false
15 310,572 false
16 853,467 false
17 2,356,779 false
18 6,536,382 false
19 18,199,284 false
20 50,852,019 false
21 142,547,559 false
22 400,763,223 false
23 1,129,760,415 false
24 3,192,727,797 false
25 9,043,402,501 false
26 25,669,818,476 false
27 73,007,772,802 false
28 208,023,278,209 false
29 593,742,784,829 false
30 1,697,385,471,211 false
31 4,859,761,676,391 false
32 13,933,569,346,707 false
33 40,002,464,776,083 false
34 114,988,706,524,270 false
35 330,931,069,469,828 false
36 953,467,954,114,363 true
37 2,750,016,719,520,991 false
38 7,939,655,757,745,265 false
39 22,944,749,046,030,949 false
40 66,368,199,913,921,497 false
41 192,137,918,101,841,817 false
</pre>
=={{header|F_Sharp|F#}}==
| |||