Brilliant numbers: Difference between revisions

Added C++ solution
m (Promote. multiple implementations, no questions)
(Added C++ solution)
Line 29:
 
 
 
=={{header|C++}}==
{{libheader|Primesieve}}
<lang cpp>#include <algorithm>
#include <chrono>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <locale>
#include <vector>
 
#include <primesieve.hpp>
 
auto get_primes_by_digits(uint64_t limit) {
primesieve::iterator pi;
std::vector<std::vector<uint64_t>> primes_by_digits;
std::vector<uint64_t> primes;
for (uint64_t p = 10; p < limit;) {
uint64_t prime = pi.next_prime();
if (prime > p) {
primes_by_digits.push_back(std::move(primes));
p *= 10;
}
primes.push_back(prime);
}
return primes_by_digits;
}
 
int main() {
std::cout.imbue(std::locale(""));
 
auto start = std::chrono::high_resolution_clock::now();
 
auto primes_by_digits = get_primes_by_digits(1000000000);
 
std::cout << "First 100 brilliant numbers:\n";
std::vector<uint64_t> brilliant_numbers;
for (const auto& primes : primes_by_digits) {
for (auto i = primes.begin(); i != primes.end(); ++i)
for (auto j = i; j != primes.end(); ++j)
brilliant_numbers.push_back(*i * *j);
if (brilliant_numbers.size() >= 100)
break;
}
std::sort(brilliant_numbers.begin(), brilliant_numbers.end());
for (size_t i = 0; i < 100; ++i) {
std::cout << std::setw(5) << brilliant_numbers[i]
<< ((i + 1) % 10 == 0 ? '\n' : ' ');
}
 
std::cout << '\n';
uint64_t power = 10;
size_t count = 0;
for (size_t p = 1; p < 2 * primes_by_digits.size(); ++p) {
const auto& primes = primes_by_digits[p / 2];
size_t position = count + 1;
uint64_t sqrt = static_cast<uint64_t>(std::ceil(std::sqrt(power)));
uint64_t min_product = 0;
for (auto i = primes.begin(); i != primes.end(); ++i) {
uint64_t p1 = *i;
auto j = std::lower_bound(i, primes.end(), (power + p1 - 1) / p1);
if (j != primes.end()) {
uint64_t p2 = *j;
uint64_t product = p1 * p2;
if (min_product == 0 || product < min_product)
min_product = product;
position += std::distance(i, j);
}
if (p1 >= sqrt)
break;
}
std::cout << "First brilliant number >= 10^" << p << " is "
<< min_product << " at position " << position << '\n';
power *= 10;
if (p % 2 == 1) {
size_t size = primes.size();
count += size * (size + 1) / 2;
}
}
 
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration(end - start);
std::cout << "\nElapsed time: " << duration.count() << " seconds\n";
}</lang>
 
{{out}}
<pre>
First 100 brilliant numbers:
4 6 9 10 14 15 21 25 35 49
121 143 169 187 209 221 247 253 289 299
319 323 341 361 377 391 403 407 437 451
473 481 493 517 527 529 533 551 559 583
589 611 629 649 667 671 689 697 703 713
731 737 767 779 781 793 799 803 817 841
851 869 871 893 899 901 913 923 943 949
961 979 989 1,003 1,007 1,027 1,037 1,067 1,073 1,079
1,081 1,121 1,139 1,147 1,157 1,159 1,189 1,207 1,219 1,241
1,247 1,261 1,271 1,273 1,333 1,343 1,349 1,357 1,363 1,369
 
First brilliant number >= 10^1 is 10 at position 4
First brilliant number >= 10^2 is 121 at position 11
First brilliant number >= 10^3 is 1,003 at position 74
First brilliant number >= 10^4 is 10,201 at position 242
First brilliant number >= 10^5 is 100,013 at position 2,505
First brilliant number >= 10^6 is 1,018,081 at position 10,538
First brilliant number >= 10^7 is 10,000,043 at position 124,364
First brilliant number >= 10^8 is 100,140,049 at position 573,929
First brilliant number >= 10^9 is 1,000,000,081 at position 7,407,841
First brilliant number >= 10^10 is 10,000,600,009 at position 35,547,995
First brilliant number >= 10^11 is 100,000,000,147 at position 491,316,167
First brilliant number >= 10^12 is 1,000,006,000,009 at position 2,409,600,866
First brilliant number >= 10^13 is 10,000,000,000,073 at position 34,896,253,010
First brilliant number >= 10^14 is 100,000,380,000,361 at position 174,155,363,187
First brilliant number >= 10^15 is 1,000,000,000,000,003 at position 2,601,913,448,897
 
Elapsed time: 0.160985 seconds
</pre>
 
=={{header|Go}}==
1,777

edits