Brilliant numbers are a subset of semiprime numbers. Specifically, they are numbers that are the product of exactly two prime numbers that both have the same number of digits when expressed in base 10.

Brilliant numbers are useful in cryptography and when testing prime factoring algorithms.



E.G.
 3 × 3 (9) is a brilliant number. 
 2 × 7 (14) is a brilliant number.
 113 × 691 (78083) is a brilliant number.
 2 × 31 (62) is semiprime, but is not a brilliant number (different number of digits in the two factors).


Task
 Find and display the first 100 brilliant numbers.
 For the orders of magnitude 1 through 6, find and show the first brilliant number greater than or equal to the order of magnitude, and, its position in the series (or the count of brilliant numbers up to that point).


Stretch
 Continue for larger orders of magnitude.


See also
 Numbers Aplenty - Brilliant numbers
 OEIS:A078972 - Brilliant numbers: semiprimes whose prime factors have the same number of decimal digits


#include <algorithm>
#include <chrono>
#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 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 >= p2)
                    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";
}