Segmented Sieve in C

Algorithms: Number Theory November 15, 2026 C

A segmented sieve marks composites only inside a requested interval, reducing memory compared with sieving all the way to its upper endpoint..

c 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#include <errno.h>
// Segmented Sieve in C
//
// PURPOSE
// A segmented sieve marks composites only inside a requested interval, reducing memory
// compared with sieving all the way to its upper endpoint.
//
// METHOD
// Sieve base primes up to square root of high. For each prime, mark its multiples in
// [low,high], starting no earlier than p squared. Count unmarked values at least two.
//
// COMPLEXITY
// O(sqrt(high) log log high + (high-low+1) log log high) time, O(sqrt(high)+high-low+1)
// space.
//
// CONTRACT
// 0 <= low <= high <= 1000000. Returns number of primes in the inclusive interval.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// C99: checked calloc/free workspace, const input pointers, explicit size_t lengths. Errors
// return INT_MIN with errno=EINVAL, ERANGE, or ENOMEM. Check errno before using a result.
// Input/output arrays must not alias. No variable-length stack arrays.
//
// EXAMPLE
// Expected return: 6.
// Run: gcc -std=c99 -O2 example.c -o example && ./example
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

static int alg_min(int a, int b) { return a < b ? a : b; }
static int alg_max(int a, int b) { return a > b ? a : b; }
static int alg_checked(int64_t v, int *error) {
    if (v < INT_MIN || v > INT_MAX) { *error = 1; return 0; }
    return (int)v;
}
static int alg_add(int a, int b, int *e) { return alg_checked((int64_t)a+b,e); }
static int alg_sub(int a, int b, int *e) { return alg_checked((int64_t)a-b,e); }
static int alg_mul(int a, int b, int *e) { return alg_checked((int64_t)a*b,e); }

int segmented_sieve(int low, int high) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    int *base = NULL;
    int *marked = NULL;
    if (!(((low >= 0) && (low <= high) && (high <= 1000000)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int limit = 1;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    while (1) {
        int alg_condition = (limit <= (high / limit));
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (!alg_condition) break;
        limit = alg_add(limit, 1, &alg_error);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    }
    {
        int alg_length = alg_add(limit, 1, &alg_error);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_length < 0 || alg_length > 4000000) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
        base = calloc((size_t)(alg_length ? alg_length : 1), sizeof(*base));
        if (!base) { errno = ENOMEM; alg_result = INT_MIN; goto alg_cleanup; }
    }
    {
        int alg_length = alg_add(alg_sub(high, low, &alg_error), 1, &alg_error);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_length < 0 || alg_length > 4000000) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
        marked = calloc((size_t)(alg_length ? alg_length : 1), sizeof(*marked));
        if (!marked) { errno = ENOMEM; alg_result = INT_MIN; goto alg_cleanup; }
    }
    int p = 2;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int multiple = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int count = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int i = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    while (1) {
        int alg_condition = (p < limit);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (!alg_condition) break;
        int alg_condition_1 = (base[p] == 0);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_condition_1) {
            multiple = alg_mul(p, p, &alg_error);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            while (1) {
                int alg_condition = (multiple < limit);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                if (!alg_condition) break;
                base[multiple] = 1;
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                multiple = alg_add(multiple, p, &alg_error);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            }
            multiple = alg_max(alg_mul(p, p, &alg_error), alg_mul((alg_sub(alg_add(low, p, &alg_error), 1, &alg_error) / p), p, &alg_error));
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            while (1) {
                int alg_condition = (multiple <= high);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                if (!alg_condition) break;
                marked[alg_sub(multiple, low, &alg_error)] = 1;
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                multiple = alg_add(multiple, p, &alg_error);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            }
        }
        p = alg_add(p, 1, &alg_error);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    }
    i = alg_max(2, low);
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    while (1) {
        int alg_condition = (i <= high);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (!alg_condition) break;
        int alg_condition_2 = (marked[alg_sub(i, low, &alg_error)] == 0);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_condition_2) {
            count = alg_add(count, 1, &alg_error);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        }
        i = alg_add(i, 1, &alg_error);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    }
    alg_result = count;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    goto alg_cleanup;
alg_cleanup:
    free(base);
    free(marked);
    return alg_result;
}

int main(void) {
    int low = 10;
    int high = 30;
    int result = segmented_sieve(low, high);
    printf("%d\n", result);
    if (errno) { perror("algorithm"); return 1; }
    return 0;
}

Related Posts

Euclidean GCD in C#
Euclidean GCD in C#
Euclidean GCD in C++
Euclidean GCD in C++
Euclidean GCD in C
Euclidean GCD in C
Euclidean GCD in Python
Euclidean GCD in Python
Euclidean GCD in JavaScript
Euclidean GCD in JavaScript
Euclidean GCD in PHP
Euclidean GCD in PHP