Блог

Я хочу запустить программу (c ), в которой я храню массив, скажем, размером 10000 из первых 10000 простых чисел, которые я вызываю int prime[10000] . Теперь либо я мог бы начать писать первые 10000 простых чисел вручную и инициализировать массив, как int prime[10000] = { 2,3,5....} , но, как вы можете себе представить, это займет некоторое время.

Вместо этого то, что я делаю прямо сейчас, это то, что у меня есть следующий код в файле 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;
            }
        }
    }
}
 

Затем объявление функции инициализации и т.д. в prime.h

 extern int prime[];

void init_prime();
 

и, наконец, моя основная программа

 #include <iostream>

#include "prime.h"

int main() {
    init_prime();

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

Это работает абсолютно нормально и все такое, но когда я запускаю программу, инициализация простого массива занимает пару секунд. Есть ли способ инициализировать этот массив во время компиляции с помощью constexpr, чтобы мне не приходилось ждать пару секунд при каждом запуске программы?

Из того, что я прочитал, я должен иметь возможность поместить constexpr перед void init_prime() в prime.cpp потому что он может быть оценен во время компиляции. Если я это сделаю, компилятор скажет мне, что я также должен поместить constexpr перед bool is_prime(int i) .

Однако, если я это сделаю, я больше не смогу вызывать функцию в main . Это выдает мне ошибку компоновщика: «неопределенная ссылка на `init_prime()'». Не имеет значения, помещаю ли я constexpr перед объявлением init_prime() в заголовочном файле. Он по-прежнему выдает мне ту же ошибку компоновщика.

Если constexpr не подходит для использования, то есть ли другой способ инициализировать этот массив во время компиляции?

Если я помещу все в main.cpp файл, затем это работает, но я не получаю ускорения, и это все равно занимает пару секунд. Я использую mingw64 для компиляции, если это имеет значение, и я компилирую без оптимизации.

Вместо C-array используйте 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();
 

ДЕМОНСТРАЦИЯ

Вам повезло, так как я реализовал что-то вроде около двух лет назад, используя решето Эратосфена:

 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 amp;amp; oddPrimes[x/2];
    }
    
    bool isPrimeInRange(size_t x) const
    {
        return x <= max() amp;amp; isPrime(x);
    }
    
    std::optional<size_t> next(size_t x) const
    {
        auto index = (x   1) / 2;
        while (index < oddPrimes.size() amp;amp; !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

У вас уже есть код для генерации простых чисел. Вы можете вывести их в файл primes.txt , разделенный запятой. Затем включите этот файл в свою программу для инициализации массива.

Т.е. генерировать primes.txt (с таким количеством простых чисел, как вам нравится):

 2, 3, 5, 7, 11
 

Затем включите этот файл для инициализации массива:

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