Frobenius numbers: Difference between revisions
Added C++ solution
Catskill549 (talk | contribs) (added AWK) |
(Added C++ solution) |
||
Line 136:
Calculated 167 Frobenius numbers of consecutive primes under 1,000,000, of which 25 were under 10,000</pre>
=={{header|C++}}==
{{libheader|Primesieve}}
<lang cpp>#include <cstdint>
#include <iomanip>
#include <iostream>
#include <primesieve.hpp>
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;
}
int main() {
const uint64_t limit = 1000000;
std::cout << "Frobenius numbers less than " << limit
<< " (asterisk marks primes):\n";
primesieve::iterator it;
uint64_t prime1 = it.next_prime();
for (int count = 1;; ++count) {
uint64_t prime2 = it.next_prime();
uint64_t frobenius = prime1 * prime2 - prime1 - prime2;
if (frobenius >= limit)
break;
std::cout << std::setw(6) << frobenius
<< (is_prime(frobenius) ? '*' : ' ')
<< (count % 10 == 0 ? '\n' : ' ');
prime1 = prime2;
}
std::cout << '\n';
}</lang>
{{out}}
<pre>
Frobenius numbers less than 1000000 (asterisk marks primes):
1 7* 23* 59* 119 191* 287 395 615 839*
1079 1439* 1679 1931* 2391 3015 3479 3959 4619 5039*
5615 6395 7215 8447* 9599 10199 10811 11447* 12095 14111
16379 17679 18767 20423 22199 23399* 25271 26891* 28551 30615
32039 34199 36479* 37631 38807 41579* 46619* 50171 51527 52895
55215 57119* 59999* 63999 67071 70215 72359 74519 77279* 78959
82343 89351 94859 96719 98591 104279 110879* 116255 120407 122495
126015 131027 136151 140615 144395 148215 153647 158399 163199* 170543
175559 180599 185759 189215 193595 198015 204287 209759 212519 215291
222747 232307* 238139 244019 249995 255015 264159 271439 281879 294839
303575 312471 319215 323759* 328319 337535 346911 354015 358799 363599
370871* 376991 380687 389339 403199 410879 414731* 421191 429015 434279
443519 454271 461031 470579* 482999 495599 508343 521267* 531431 540215
547595 556499 566999* 574559 583679 592895 606791* 625655 643167 654479
664199* 674039 678971* 683927 693863 713975 729311 734447 739595 755111
770879 776159* 781451 802715 824459* 835379* 851903 868607 879839* 889239
900591 919631* 937019 946719 958431 972179 986039
</pre>
=={{header|Factor}}==
| |||