Blum integer: Difference between revisions
Content added Content deleted
m (Code using an iImproved algorithm.) |
(New post.) |
||
Line 217: | Line 217: | ||
<pre> |
<pre> |
||
Same as Wren example. |
Same as Wren example. |
||
</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="java"> |
|||
#include <algorithm> |
|||
#include <cstdint> |
|||
#include <iomanip> |
|||
#include <iostream> |
|||
#include <vector> |
|||
bool is_prime_type_3(const int32_t number) { |
|||
if ( number < 2 ) return false; |
|||
if ( number % 2 == 0 ) return false; |
|||
if ( number % 3 == 0 ) return number == 3; |
|||
for ( int divisor = 5; divisor * divisor <= number; divisor += 2 ) { |
|||
if ( number % divisor == 0 ) { return false; } |
|||
} |
|||
return number % 4 == 3; |
|||
} |
|||
int32_t least_prime_factor(const int32_t number) { |
|||
if ( number == 1 ) { return 1; } |
|||
if ( number % 3 == 0 ) { return 3; } |
|||
if ( number % 5 == 0 ) { return 5; } |
|||
for ( int divisor = 7; divisor * divisor <= number; divisor += 2 ) { |
|||
if ( number % divisor == 0 ) { return divisor; } |
|||
} |
|||
return number; |
|||
} |
|||
int main() { |
|||
int32_t blums[50]; |
|||
int32_t blum_count = 0; |
|||
int32_t last_digit_counts[10] = {}; |
|||
int32_t number = 1; |
|||
while ( blum_count < 400'000 ) { |
|||
const int32_t prime = least_prime_factor(number); |
|||
if ( prime % 4 == 3 ) { |
|||
const int32_t quotient = number / prime; |
|||
if ( quotient != prime && is_prime_type_3(quotient) ) { |
|||
if ( blum_count < 50 ) { |
|||
blums[blum_count] = number; |
|||
} |
|||
last_digit_counts[number % 10] += 1; |
|||
blum_count += 1; |
|||
if ( blum_count == 50 ) { |
|||
std::cout << "The first 50 Blum integers:" << std::endl; |
|||
for ( int32_t i = 0; i < 50; ++i ) { |
|||
std::cout << std::setw(3) << blums[i] << ( ( i % 10 == 9 ) ? "\n" : " " ); |
|||
} |
|||
std::cout << std::endl; |
|||
} else if ( blum_count == 26'828 || blum_count % 100'000 == 0 ) { |
|||
std::cout << "The " << std::setw(6) << blum_count << "th Blum integer is: " |
|||
<< std::setw(7) << number << std::endl; |
|||
if ( blum_count == 400'000 ) { |
|||
std::cout << "\nPercent distribution of the first 400000 Blum integers:" << std::endl; |
|||
for ( const int32_t& i : { 1, 3, 7, 9 } ) { |
|||
std::cout << " " << std::setw(6) << std::setprecision(5) |
|||
<< (double) last_digit_counts[i] / 4'000 << "% end in " << i << std::endl; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
number += ( number % 5 == 3 ) ? 4 : 2; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
The first 50 Blum integers: |
|||
21 33 57 69 77 93 129 133 141 161 |
|||
177 201 209 213 217 237 249 253 301 309 |
|||
321 329 341 381 393 413 417 437 453 469 |
|||
473 489 497 501 517 537 553 573 581 589 |
|||
597 633 649 669 681 713 717 721 737 749 |
|||
The 26828th Blum integer is: 524273 |
|||
The 100000th Blum integer is: 2075217 |
|||
The 200000th Blum integer is: 4275533 |
|||
The 300000th Blum integer is: 6521629 |
|||
The 400000th Blum integer is: 8802377 |
|||
Percent distribution of the first 400000 Blum integers: |
|||
25.001% end in 1 |
|||
25.017% end in 3 |
|||
24.997% end in 7 |
|||
24.985% end in 9 |
|||
</pre> |
</pre> |
||