Motzkin numbers: Difference between revisions
Content added Content deleted
(→{{header|Fermat}}: -add output) |
(Added C++ solution) |
||
Line 289: | Line 289: | ||
14,996,791,899,280,244,858,336,604 |
14,996,791,899,280,244,858,336,604 |
||
43,881,711,243,248,048,262,611,670 </pre> |
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#}}== |
=={{header|F_Sharp|F#}}== |