Решето Эратосфена

#include <stdio.h>
#include <math.h>
 
#define true 1
#define false 0
 
#pragma region bitvector
 
#include <string.h>
#include <limits.h>
#include <stdlib.h>
 
#define BYTES sizeof(size_t)
#define BITS (BYTES * 8)
#define BITVECTOR_SIZE(n) ( n / BITS + (n % BITS != 0) )
 
#define BITVECTOR_INIT(vector_name, n)  \
    size_t * vector_name = (size_t*) malloc(BITVECTOR_SIZE(n) * BYTES); 
 
#define BITVECTOR_CLEAR(vector_name, n) \
    memset(vector_name, 0, BITVECTOR_SIZE(n) * BYTES);
 
#define ARR_INDEX(index) (index / (sizeof(size_t) * 8) )
#define BIT_INDEX(index) (index % (sizeof(size_t) * 8) )
 
#define BIT_TEST(vector, index) \
    ( vector[ARR_INDEX(index)] & (1 << BIT_INDEX(index)) )
 
#define SIZE_T_MAX ( ~( (size_t) 0) )
 
 
#define BIT_SET_TRUE(vector, index) \
    vector[ARR_INDEX(index)] |= 1 << (size_t) BIT_INDEX(index);
 
#define BIT_SET(vector, index, value)                       \
    if (value) vector[ARR_INDEX(index)] |= 1 << (size_t) BIT_INDEX(index);          \
    else vector[ARR_INDEX(index)] &= SIZE_T_MAX ^ (1 << (size_t) BIT_INDEX(index));
 
#define BIT_XOR(vector, index)  \
    vector[ARR_INDEX(index)] ^= 1 << BIT_INDEX(index);
 
#define BITVECTOR_FREE(vector) \
    free(vector);
 
#pragma endregion
 
FILE *output;
 
int sieve_first_block(unsigned int *primes, int n)
{
    primes[0] = 2;
    int counter = 1;
 
    int sq = (int) (sqrt(1.0 * n) + 1e-7);
 
    n = (n - 1) / 2;
 
    BITVECTOR_INIT(sieve, n)
        BITVECTOR_CLEAR(sieve, n)
 
        for (int i = 3; i <= sq; i += 2)
        {
            if (!BIT_TEST(sieve, i / 2))
            {
                primes[counter++] = i;
 
                for (int j = i * i / 2; j <= n; j += i)
                {
                    BIT_SET_TRUE(sieve, j)
                }
            }
        }
 
        for (int i = (sq + 1 + (sq % 2 != 0)) / 2; i <= n; ++i)
        {
            if (!BIT_TEST(sieve, i))
                primes[counter++] = 2 * i + 1;
        }
 
        BITVECTOR_FREE(sieve)
 
            return counter;
}
 
void segmented_sieve(int n)
{
    int block_size = 250000;
 
    int primes_size = 1229;
 
    unsigned int primes[100500];
 
    int real_primes_size = sieve_first_block(primes, block_size);
 
    for (int i = 0; i < real_primes_size; i += 100)
    {
        fprintf(output, "%d ", primes[i]);
    }
 
    int counter = real_primes_size % 100;
 
    block_size = (block_size) / 2;
 
    BITVECTOR_INIT(sieve, block_size)
 
        fflush(output);
 
    for (int block_begin = block_size; block_begin + block_size <= n / 2; block_begin += block_size)
    {
        int block_end = block_begin + block_size;
 
        BITVECTOR_CLEAR(sieve, block_size)
 
            for (int i = 1; i < primes_size; ++i)
            {
                int current_prime = primes[i];
 
                int start_index = block_begin * 2 / current_prime * current_prime + current_prime * (block_begin * 2 % current_prime != 0);
 
                if (start_index % 2 == 0)
                    start_index += current_prime;
 
                start_index /= 2;
 
                start_index -= block_begin;
 
                for (int j = start_index; j < block_size; j += current_prime)
                {
                    BIT_SET_TRUE(sieve, j)
                }
            }
 
            for (int i = 0; i < block_size; ++i)
            {
                if (!BIT_TEST(sieve, i))
                {
                    if (++counter % 100 == 1)
                    {
                        fprintf(output, "%d ", 2 * (i + block_begin) + 1);
                    }
                }
            }
    }
 
    BITVECTOR_FREE(sieve)
}
 
int main()
{
    output = stdout;
    //output = fopen("output.txt", "w");
 
    segmented_sieve(100 * 1000 * 1000);
 
    return 0;
}