АПДЕЙТ Как справедливо указали в комментарии, это не решето Эратосфена. Настоящее решето с предпросмотром и вычеркиванием составных чисел на больших числах работает в разы быстрее и занимает меньше памяти.

Вот заготовка последовательного перебора простых чисел решетом Эратосфена. Когда при переборе находится очередное простое число, оно добавляется в решето.

#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <math.h>

typedef uint32_t prime_t;

struct Sieve
{
    size_t count;
    prime_t *primes;
};

prime_t small_primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
                          47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

void init_Sieve(struct Sieve *sieve)
{
    sieve->count = sizeof(small_primes) / sizeof(small_primes[0]);
    sieve->primes = (prime_t *)malloc(sieve->count * sizeof(small_primes[0]));

    memcpy(sieve->primes, small_primes, sieve->count * sizeof(prime_t));
}

void dispose_Sieve(struct Sieve *sieve)
{
    free(sieve->primes);
}

void append_Sieve(struct Sieve *sieve, prime_t prime)
{
    sieve->count++;
    sieve->primes = realloc(sieve->primes, sieve->count * sizeof(prime_t));
    sieve->primes[sieve->count - 1] = prime;
}

prime_t last_Sieve(struct Sieve *sieve)
{
    return sieve->primes[sieve->count - 1];
}

uint32_t int_sqrt(uint64_t n)
{
    return (uint32_t)floor(sqrt(n));
}

bool is_prime_Sieve(struct Sieve *sieve, uint64_t n)
{
    int32_t limit = int_sqrt(n);
    for (size_t i = 0; i < sieve->count; i++)
    {
        uint32_t p = sieve->primes[i];
        if (p > limit)
        {
            return true;
        }
        if (n % sieve->primes[i] == 0)
        {
            return false;
        }
    }
}

prime_t next_prime_Sieve(struct Sieve *sieve)
{
    uint64_t candidate = last_Sieve(sieve) + 2;
    while (true)
    {
        if (is_prime_Sieve(sieve, candidate))
        {
            return candidate;
        }
        candidate += 2;
    }
}

#include <stdio.h>
#include <unistd.h>

int main(int argc, char const *argv[])
{
    int num = 100;
    struct Sieve sieve;
    init_Sieve(&sieve);
    for (size_t i = 0; i < num; i++)
    {
        printf("%d\n", sieve.primes[i]);
    }

    num -= sieve.count;

    for (int i = 0; i < num; i++)
    {
        prime_t prime = next_prime_Sieve(&sieve);
        printf("new prime: %d\n", prime);
        append_Sieve(&sieve, prime);
    }
    dispose_Sieve(&sieve);
    return 0;
}

UPDATE

тут ниже было про ускорить. Как оказалось, предложенные рецепты не сильно помогают.

На стареньком процессоре Xeon сделал небольшой бенчмарк: поиск первого миллиона простых чисел

sieve_1_1: 4.510699915 s
sieve_100_1: 4.502938856 s
sieve_100_1.4: 4.501762310 s
sieve2: 4.498788561 s
Sieve.cpp: 4.495656952 s
Sieve2.cpp: 4.495942813 s

• sieve_1_1 лобовой перебор без оптимизации.
• sieve_100_1 каждый realloc прибавляет ёмкость в 10000 чисел.
• sieve_100_1.4: на каждой итерации шаг realloc увеличивается в 1.4 раза.
• sieve2 тянет массив квадратов простых чисел, чтобы не извлекать квадратный корень при переборе делителей.
• Sieve.cpp и Sieve2.cpp делают всё то же самое, что sieve_1_1 и sieve2, но используется для хранения std::vector

Как видно, все алгоритмы работают примерно одинаково.

СТАРЫЙ ТЕКСТ

Как можно ускорить. Во-первых, добавление нового простого довольно дорого, каждый раз делается realloc. Можно добавить cap и при очередном realloc увеличивать cap на константу или множителем.

Во-вторых, при поиске простых чисел можно перебирать не каждое нечетное число, а пропуская те, которые делятся на 2, 3, 5. Это увеличит скорость перебора примерно в два раза. Если интересно, я поищу - где-то в загашниках у меня есть таблички, как нужно смещаться в зависимости от того, на какие числа не хотим делить. Составляются элементарно через китайскую теорему об остатках.

В третьих, вместо извлечения квадратного корня можно вместе с табличкой простых чисел тащит табличку квадратов простых чисел. Это позволит избавиться от вычисления квадратного корня при поиске делителей.

О я вижу, здесь речь зашла о решете Эратосфена. Принцип работы, вычеркиваем ненужные

#include <stdio.h>
#include <stdlib.h>

void sitoera(int n) {
    // Создаем массив для хранения информации о простоте чисел
    // здесь индекс массива будет числом, значнеие массива будет говорить оно простое True или нет False
    // размеры тут самому определить

    int* stored_primes = (int*)malloc((n + 1) * sizeof(int));
    for (int i = 0; i <= n; i++) {
        stored_primes[i] = 1; // Изначально все элементы True
    }
    stored_primes[0] = stored_primes[1] = 0; // 0 и 1 не являются простыми числами False

    for (int p = 2; p * p <= n; p++) { //пробегаем весь массив
        if (stored_primes[p]) {              // если значение массива True
            for (int i = p * p; i <= n; i += p) {  // пробегаем по индексам кратным p 
                stored_primes[i] = 0; // Отмечаем кратные p как непростые False
            }
        }
    }
    //Когда весь массив заполнен
    // Выводим все простые числа которые True
    printf("Простые числа до %d:\n", n);
    for (int i = 2; i <= n; i++) {
        if (stored_primes[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");

    // Освобождаем память
    free(stored_primes);
}

int main() {
    int n = 10000; // Задайте верхний предел для поиска простых чисел
          sitoera(n);
    return 0;
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039

Требования к скорости алгоритма

Когда следующее простое число найдено и задача решена, следующий шаг – перераспределение корзин в хеш-таблице. Которое займет O(p) времени, где p – найденное простое число. То есть, нам подходит любой алгоритм, который отыскивает число быстрее чем за линейное время. Потому что время его работы будет ничтожным на фоне времени перестроения таблицы. Это оценка с точки зрения O-большого, для маленьких размеров ещё важна константа.

Проверка всех делителей до √n требует времени около √n · log n, где первый множитель – проверка одного числа, второй множитель – среднее количество чисел, которое нужно проверить до момента как мы отыщем простое. Добавлю что эта оценка сильно завышена, так как проверка составных чисел всегда заканчивается раньше, чем мы дойдём до √n. И часто это проверка заканчивается намного раньше.

NB С этим связано следующее наблюдение: если исключить из перебора все чётные кандидаты в простые, скорость поиска следующего простого не вырастет в два раза. Потому что мы отбрасываем те числа, которые делятся на два, а они почти сразу выходят из цикла перебора делителей. Это не значит что эта оптимизация не нужна, это значит, что не надо ждать от неё слишком многого. В два раза быстрее не будет.

Я согласен, что надо стремиться к написанию быстрого поиска, но без фанатизма. Чрезмерное усложнение не приведёт к заметному ускорению работы с таблицами, но может привести к тяжёлым в отладке ошибкам.

Требования к параллельному исполнению

Остановитесь, если вам хочется сделать глобальный изменяющийся список простых чисел для ускорения поиска. Мы говорим об изменении размера хеш-таблиц. Их бывает много и они работают в разных нитках. То есть, для расчёта нового простого числа и помещения его в глобальный кэш, этот кэш надо будет защищать от конкурентного доступа. Изменение крохотной таблички в вашей нитке может быть заторможено ожиданием, пока в другой нити громадная таблица отыщет очередной миллион простых чисел для своего нового размера. Это неприятный побочный эффект.

Желательно обойтись без растущих таблиц простых чисел.

Вывод

Простой поиск до корня решает задачу, код прост, время работы приемлемо (вы никак не сделаете так чтобы увидеть улучшения в профилировке). Можно не проверять чётные кандидаты и чётные делители, так как это не слишком усложняет код и улучшает константу. Но больше ничего делать не надо, задача уже решена и решена хорошо.