Strong and weak primes: Difference between revisions
Content added Content deleted
(Added C++ solution) |
|||
Line 170: | Line 170: | ||
There are 37,780 weak primes below 1,000,000 |
There are 37,780 weak primes below 1,000,000 |
||
There are 321,750 weak primes below 1,000,000</pre> |
There are 321,750 weak primes below 1,000,000</pre> |
||
=={{header|C++}}== |
|||
<lang cpp>#include <iostream> |
|||
#include <iomanip> |
|||
#include <locale> |
|||
#include <sstream> |
|||
#include <vector> |
|||
int main() |
|||
{ |
|||
const int limit1 = 1000000; |
|||
const int limit2 = 10000000; |
|||
const int max_print[2] = { 36, 37 }; |
|||
const int array_size = limit2 + 100; |
|||
// find the prime numbers up to array_size |
|||
std::vector<bool> isprime(array_size, true); |
|||
isprime[0] = isprime[1] = false; |
|||
for (int p = 2; p * p < array_size; ++p) |
|||
{ |
|||
if (isprime[p]) |
|||
{ |
|||
for (int i = p * p; i < array_size; i += p) |
|||
isprime[i] = false; |
|||
} |
|||
} |
|||
// write numbers with groups of digits separated according to the system default locale |
|||
std::cout.imbue(std::locale("")); |
|||
std::cout << std::fixed; |
|||
// count and print strong/weak prime numbers |
|||
int count1[2] = { 0 }; |
|||
int count2[2] = { 0 }; |
|||
std::ostringstream out[2]; |
|||
const char* strength[2] = { "strong", "weak" }; |
|||
int p1 = 2, p2 = 3; |
|||
for (int p3 = 5; p2 < limit2; ++p3) |
|||
{ |
|||
if (!isprime[p3]) |
|||
continue; |
|||
int diff = p1 + p3 - 2 * p2; |
|||
int index = diff < 0 ? 0 : (diff > 0 ? 1 : -1); |
|||
if (index != -1) |
|||
{ |
|||
++count2[index]; |
|||
if (p2 < limit1) |
|||
++count1[index]; |
|||
if (count2[index] <= max_print[index]) |
|||
{ |
|||
if (count2[index] > 1) |
|||
out[index] << ' '; |
|||
out[index] << p2; |
|||
} |
|||
} |
|||
p1 = p2; |
|||
p2 = p3; |
|||
} |
|||
for (int i = 0; i < 2; ++i) |
|||
{ |
|||
std::cout << "First " << max_print[i] << " " << strength[i] << " primes: " << out[i].str() << '\n'; |
|||
std::cout << "Number of " << strength[i] << " primes below " << limit1 << ": " << count1[i] << '\n'; |
|||
std::cout << "Number of " << strength[i] << " primes below " << limit2 << ": " << count2[i] << '\n'; |
|||
} |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
First 36 strong primes: 11 17 29 37 41 59 67 71 79 97 101 107 127 137 149 163 179 191 197 223 227 239 251 269 277 281 307 311 331 347 367 379 397 419 431 439 |
|||
Number of strong primes below 1,000,000: 37,723 |
|||
Number of strong primes below 10,000,000: 320,991 |
|||
First 37 weak primes: 3 7 13 19 23 31 43 47 61 73 83 89 103 109 113 131 139 151 167 181 193 199 229 233 241 271 283 293 313 317 337 349 353 359 383 389 401 |
|||
Number of weak primes below 1,000,000: 37,780 |
|||
Number of weak primes below 10,000,000: 321,750 |
|||
</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |