Strong and weak primes: Difference between revisions
Added C++ solution
(Added C++ solution) |
|||
Line 170:
There are 37,780 weak primes below 1,000,000
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}}==
| |||