I want to run a program (c ) where I keep an array of say size 10000 of the first 10000 primes which I call int prime[10000]. Now either I could start writing the first 10000 primes by hand and initialize the array like int prime[10000] = { 2,3,5....} but as you can imagine this would take a time.

Instead what I'm doing right now is I have the following code in a file prime.cpp

const int prime_size = 10000;

int prime[prime_size];

bool is_prime(int i) {
    for (int j = 2;j < i;j  ) {
        if (i % j == 0) {
            return false;
        }
    }
    return true;
}

void init_prime() {
    int prime_counter = 1;
    prime[0] = 2;
    while (prime_counter < prime_size) {
        int counter = prime[prime_counter - 1];
        while (true) {
            counter  ;
            if (is_prime(counter)) {
                prime[prime_counter] = counter;
                prime_counter  ;
                break;
            }
        }
    }
}

Then a declaration of the init function etc in prime.h

extern int prime[];

void init_prime();

and finally my main program

#include <iostream>

#include "prime.h"

int main() {
    init_prime();

    std::cout << prime[8] << std::endl;
}

This works totally fine and all, but when I start the program it takes a couple of seconds to initialize the prime array. Is there a way to initialize this array at compile time using constexpr so I don't have to wait a couple of seconds each time I run the program?

From what I have read I should be able to put constexpr in front of void init_prime() in prime.cpp because it can be evaluated at compile time. If I do this the compiler tells me I have to put constexpr in front of bool is_prime(int i) as well.

If I do this however, I can no longer call the function in main. It gives me a linker error, "undefined reference to `init_prime()'". It doesn't matter if I put constexpr in front of the declaration of init_prime() in the header file. It still gives me the same linker error.

If constexpr is not the right tool to use, then is there another way to initialize this array at compile time?

If I put everything in the main.cpp file then it works, but I get no speed up and it still takes a couple of seconds. I'm using mingw64 to compile if this matters and I'm compiling without optimizations.

CodePudding user response：

Instead of C-array, use std::array:

constexpr int prime_size = 10000;

constexpr bool is_prime(int i) {
    for (int j = 2;j < i;j  ) {
        if (i % j == 0) {
            return false;
        }
    }
    return true;
}

constexpr std::array<int, prime_size> init_primes() {
    std::array<int, prime_size> primes{};
    int prime_counter = 1;
    primes[0] = 2;
    while (prime_counter < prime_size) {
        int counter = primes[prime_counter - 1];
        while (true) {
            counter  ;
            if (is_prime(counter)) {
                primes[prime_counter] = counter;
                prime_counter  ;
                break;
            }
        }
    }
    return primes;
}

constexpr std::array<int, prime_size> primes = init_primes();

Demo

CodePudding user response：

You are lucky since I've implemented something like about two years ago using Eratosthenes sieve:

template<size_t N>
class EratostenesSive
{
public:
    constexpr EratostenesSive()
        : oddPrimes{}
    {
        std::fill(oddPrimes.begin(), oddPrimes.end(), true);
        oddPrimes[0] = false;
        
        for (size_t p = 3; p * p <= N; p  = 2) {
            if (oddPrimes[p/2]) {
                for (size_t i = p * p; i <= N; i  = 2 * p) {
                    oddPrimes[i/2] = false;
                }
            }
        }
    }
    
    bool isPrime(size_t x) const
    {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x > max()) throw std::invalid_argument("Sive limit reached");
        return x%2 != 0 && oddPrimes[x/2];
    }
    
    bool isPrimeInRange(size_t x) const
    {
        return x <= max() && isPrime(x);
    }
    
    std::optional<size_t> next(size_t x) const
    {
        auto index = (x   1) / 2;
        while (index < oddPrimes.size() && !oddPrimes[index])   index;
        if (index < oddPrimes.size()) return index * 2   1;
        return {};
    }
    
    constexpr size_t max() const {
        return N | 1;
    }
    
private:
    std::array<bool, (N   1) / 2> oddPrimes;
};

https://wandbox.org/permlink/enGXi6bRUrgGicE2

CodePudding user response：

You already have the code to generate the primes. You can output them to a file primes.txt separated by comma. Then include that file in your program to initialize the array.

I.e. generate primes.txt (with as many primes as you like):

2, 3, 5, 7, 11

Then include that file to initialize the array:

unsigned primes[] =
{
    #include "primes.txt"
};