c++ - How to generate std::array of primes up to certain maximum prime at compile-time - Stack Overflow

admin管理员组

文章数量:1122832

I am trying to generate std::array with primes up to 30. Not first 30 primes, but 2 3 5 7 11 13 17 19 23 29.

My best attempt is below and it works, but has ugly code repetition:

auto primes = make_primes(MAX_PRIME);
constexpr auto N = make_primes(MAX_PRIME).size();

Is there some way to avoid it?

Link:

#include <iostream>
#include <cstdint>
#include <vector>
#include <array>

using namespace std;

constexpr vector<int> make_primes(int max_prime) noexcept
{
    vector<int> primes;

    primes.push_back(2);
    for (int p = 3; p < max_prime; )
    {
        primes.push_back(p);

        int i;
        do {
            p += 2;

            i = 1;
            for (; i < primes.size(); ++i)
            {
                if ((p % primes[i]) == 0)
                    break;
            }
        }
        while (i != primes.size());
    }
    
    return primes;
}

constexpr int MAX_PRIME = 30;  // 2 3 5 7 11 13 17 19 23 29

constexpr auto primes {
    []() {
        auto primes = make_primes(MAX_PRIME);
        constexpr auto N = make_primes(MAX_PRIME).size();

        std::array<int, N> arr;
        for (int i = 0; i < arr.size(); ++i)
            arr[i] = primes[i];
        return arr;
    }()
};

int main()
{
    cout << primes.size() << ':';
    for (int x : primes)
        cout << ' ' << x;
    cout << endl;

    return 0;
}

I am trying to generate std::array with primes up to 30. Not first 30 primes, but 2 3 5 7 11 13 17 19 23 29.

My best attempt is below and it works, but has ugly code repetition:

auto primes = make_primes(MAX_PRIME);
constexpr auto N = make_primes(MAX_PRIME).size();

Is there some way to avoid it?

Link: https://godbolt.org/z/dTvvGj6sY

#include <iostream>
#include <cstdint>
#include <vector>
#include <array>

using namespace std;

constexpr vector<int> make_primes(int max_prime) noexcept
{
    vector<int> primes;

    primes.push_back(2);
    for (int p = 3; p < max_prime; )
    {
        primes.push_back(p);

        int i;
        do {
            p += 2;

            i = 1;
            for (; i < primes.size(); ++i)
            {
                if ((p % primes[i]) == 0)
                    break;
            }
        }
        while (i != primes.size());
    }
    
    return primes;
}

constexpr int MAX_PRIME = 30;  // 2 3 5 7 11 13 17 19 23 29

constexpr auto primes {
    []() {
        auto primes = make_primes(MAX_PRIME);
        constexpr auto N = make_primes(MAX_PRIME).size();

        std::array<int, N> arr;
        for (int i = 0; i < arr.size(); ++i)
            arr[i] = primes[i];
        return arr;
    }()
};

int main()
{
    cout << primes.size() << ':';
    for (int x : primes)
        cout << ' ' << x;
    cout << endl;

    return 0;
}

• c++
• constexpr

Share Improve this question Follow edited Nov 22, 2024 at 13:35 CommunityBot 111 silver badge asked Nov 22, 2024 at 11:18 MishkaMishka 731010 bronze badges 4

• Being able to use std::vector in constexpr allows to resuse the code as you did instead of requiring 2 similar algo, one for the size, and one to fill the array. I don't think there is a way to avoid to call the function twice currently. – Jarod42 Commented Nov 22, 2024 at 11:36
• @Jarod42, I wasn't aware that one could use std::vector in constexpr. How can it be done at compile time since it has somewhere to deal with dynamic allocation ? – edrezen Commented Nov 22, 2024 at 11:48
• @edrezen: constexpr std::vector is indeed not possible, but using std::vector in constexpr function as OP did is possible. – Jarod42 Commented Nov 22, 2024 at 11:55
• I did something like this 5 years ago: wandbox.org/permlink/ODZ2TL4VgjJv6b0c – Marek R Commented Nov 22, 2024 at 12:33

Add a comment  | 

3 Answers 3

Sorted by: Reset to default 2

The issue is that you need first to compute the size of the array before allocate it and then populate it.

A variation on your proposal is to make make_primes return as a std::pair both the computed size and a populated array (whose size is equal to 30). Then you can use the computed size as a template parameter of a cut function that will cut the array with the good size.

The difference compared to you proposal is that make_primes is called only once.

#include <array>

template<int max_prime>
constexpr auto make_primes () noexcept
{
    static_assert(max_prime>0);
    
    std::array<int,max_prime> primes {};

    int idx=0;
    primes[idx++] = 2;
    
    for (std::size_t p = 3; p < max_prime; )
    {
        primes[idx++] = p;

        int i;
        do {
            p += 2;
            i = 1;
            for (; i < idx; ++i)
            {
                if ((p % primes[i]) == 0)
                    break;
            }
        }
        while (i != idx);
    }
    
    return std::make_pair(primes,idx);
}

template<std::size_t P, std::size_t N>
constexpr auto cut (std::array<int,N> const& in)
{
    static_assert (P<=N);
    std::array<int,P> out;
    for (std::size_t i=0; i<P; i++)  { out[i] = in[i]; } 
    return out;
}

constexpr auto prinfo = make_primes<30>();
constexpr auto primes = cut<prinfo.second> (prinfo.first);

static_assert (primes.size() == 10);
static_assert (primes == std::array {2, 3, 5, 7, 11, 13, 17, 19, 23, 29});

int main()  { }

Demo

Update 1: some simplification according to @Jarod42's comment.

Update 2: a small improvement that provides a clearer API for the end user.

Update 3: a final one that relies on std::span

This is code I have lying around that does that : E.g. for first 10 numbers it will generate an array with exactly 4 values only

#include <array>
#include <iostream>

// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

namespace details
{

    template<std::size_t N>
    static constexpr auto sieve()
    {
        std::array<bool, N> is_prime{};

        for (std::size_t n = 2; n < N; ++n)
        {
            is_prime[n] = true;
        }


        for (std::size_t n = 2ul; n < N; ++n)
        {
            if (is_prime[n])
            {
                auto n2 = n * n;
                for (std::size_t m = n2; m < N; m += n)
                {
                    is_prime[m] = false;
                }
            }
        }

        return is_prime;
    }

    template<std::size_t N>
    static constexpr std::size_t count_primes(const std::array<bool, N>& is_prime)
    {
        std::size_t count{ 0ul };

        for (std::size_t n = 0; n < N; ++n)
        {
            if (is_prime[n]) ++count;
        }

        return count;
    }

    template<std::size_t N>
    static constexpr auto get_primes()
    {
        std::array<int, count_primes<N>()> primes{};
        auto is_prime = sieve<N>();

        for (std::size_t n = 0ul, i = 0ul; n < N; ++n)
        {
            if (is_prime[n])
            {
                primes[i] = static_cast<int>(n);
                ++i;
            }
        }

        return primes;
    }

} // details

template<std::size_t N>
constexpr auto make_primes()
{
    constexpr auto is_prime = details::sieve<N>();
    constexpr auto count = details::count_primes<N>(is_prime);
    std::array<int, count> primes{};

    for (std::size_t n{ 0ul }, i{ 0ul }; n < N; ++n)
    {
        if (is_prime[n])
        {
            primes[i] = static_cast<int>(n);
            ++i;
        }
    }

    return primes;
}

int main()
{
    constexpr auto primes = make_primes<10>();
    static_assert(primes.size() == 4ul);
    static_assert(primes[0] == 2);
    static_assert(primes[1] == 3);
    static_assert(primes[2] == 5);
    static_assert(primes[3] == 7);

    for (const auto prime : primes)
    {
        std::cout << prime << " ";
    }

    return 0;
}

To better explain my comment on @PepijnKramer, here's the code:

template<std::size_t N>
static constexpr auto sieve()
{
    // Compute both the prime number array and count them at the same time
    constexpr auto fc = []() {
        std::array<bool, N> is_prime{};
        std::array<int, N> tmp{};
        for (std::size_t n = 2; n < N; ++n)
            is_prime[n] = true;
        std::size_t c = 0;
        for (std::size_t n = 2ul; n < N; ++n)
        {
            if (is_prime[n])
            {
                auto n2 = n * n;
                for (std::size_t m = n2; m < N; m += n)
                {
                    is_prime[m] = false;
                }
                tmp[c++] = n;
            }
        }
        return std::make_pair(c, tmp);
    }();

    // Then strip the array to the final (used/counted) size 
    std::array<int, fc.first> result;
    for (auto i = 0; i < fc.first; i++) result[i] = fc.second[i];
    return result;
}


int main()
{
    constexpr auto a = sieve<30>();
    for (auto i : a)
       std::cout << i << std::endl;    
}

Demo

You can compute both if a number is prime and count it at the same time (in that case, you'll save it in a oversized array). Then a final step is to cut the array to the actual used numbers and return that.

Please note that this isn't optimized at all and just used as a proof of concept. The Sieve of Eratosthenes algorithm is far from being optimal, you can remove all even numbers in a very easy step and avoid creating a N sized array as a temporary storage (a N/2 array is enough for N > 2).

本文标签： cHow to generate stdarray of primes up to certain maximum prime at compiletimeStack Overflow