Sieve of Eratosthenes in C I have attempted to implement the Sieve of Eratosthenes in C. It works rather quickly with values tested up to ten million: time ./soe.out 10000000 returns real: 0m0.218s (this is of course, not including the result printing at the end which takes the majority of the time).

Is my code the most efficient it could be, and would implementing a segmented sieve instead be a good idea for improvement?

#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;math.h&gt;
#include &lt;errno.h&gt;
#include &lt;stdlib.h&gt;

#define true (1)
#define false (0)
typedef unsigned char bool;

#define MAX 10000000

/* to_int: converts a character array to an integer, returns -1 on error, -2 on out of limits */
int to_int(char* inp) {
    int len = strlen(inp);
    unsigned int out = 0, prev_out = 0, mult = 1;

    if (len == 0)
        return -1;

    for (int i = len - 1; i &gt;= 0; i--) {
        if (inp[i] &lt; 48 || inp[i] &gt; 57)
            return -1;

        prev_out = out;
        out += (inp[i] - 48) * mult;
        mult *= 10;

        /* detect wrapping */
        if (out &lt; prev_out)
            return -2;
    }

    return out;
}

int main(int argc, char **argv) {
    if (argc &lt; 2) {
        fprintf(stderr, "Syntax: number to find primes up to (max. %d)\n", MAX);
        return EXIT_FAILURE;
    }

    unsigned int max = to_int(argv[1]);

    if (max == -1) {
        fprintf(stderr, "Syntax: number to find primes up to (you typed %s, which is not a valid number)\n", argv[1]);
        return EXIT_FAILURE;
    }

    if (max &gt; MAX || max == -2) {
        printf("Warning: the number you typed was outside of the limit. It has been set to %d.\nPress the return key to continue...\n", MAX);
        max = MAX;
        getchar();
    }

    max++;

    /* Set up the list */
    bool *list = NULL;
    if ((list = malloc(max)) == NULL) {
        fprintf(stderr, "Error! Could not allocate the requested amount of memory: %s\nExiting...\n", strerror(errno));
        return EXIT_FAILURE;
    }

    memset(list, true, max);

    int iteration = 0;
    int max_sqrt = sqrt(max);

    for (int i = 2; i &lt;= max_sqrt; i++) {
        if (list[i])
            for (int j = i*i; j &lt;= max; j += i)
                list[j] = false;
    }

    for (int i = 1; i &lt; max; i++)
        if (list[i])
            printf("%d: prime\n", i);

    free(list);

    return EXIT_SUCCESS;
}
This works really well and is very easy to read! Here are some suggestions.

Don't Reinvent the Wheel

There are plenty of ways to convert a string to a number in C. There's no need to write your own. You could instead use atoi(), strtol() or sscanf().

Use the Right Comparison

You made max be an unsigned int, but then you compare it against -1 and -2. Those values are not unsigned. I would make some named constants for those comparisons. Something like:

static const unsigned int ERROR_NO_NUMBERS = UINT_MAX;
static const unsigned int ERROR_MAX_BAD_VALUE = ERROR_NO_NUMBERS - 1;


Note that the value for ERROR_NO_NUMBERS depends on the size of an int on your platform. I assumed it was 32 bits.

Prefer const to #define

Preprocessor macros created with #define are problematic. They can lead to very hard to understand code with surprising effects. For defining a constant it's not a huge deal, but it's good to get into the habit of using const for constants and inline functions for calculations when possible instead of macros because of the problems they have.

Performance

Aside from using a different algorithm, I don't see a lot of ways to improve the speed of this. One minor improvement might come from filling the array with alternating true/false values at the start so you iterate over fewer values. Something like this:

// Skip the first 4 values
list [ 0 ] = true;
list [ 1 ] = true;
list [ 2 ] = true;
list [ 3 ] = true;
// This value represents 4 bools in order false, true, false, true
const bool FALSE_TRUE_FALSE_TRUE[] = {false, true, false, true};
// Set all even values over 3 to false since we know they're divisible by 2
memset_pattern4(&amp;list [ 4 ], FALSE_TRUE_FALSE_TRUE, max - 4);


You can then skip checking for 2 and start at 3:

for (int i = 3; i &lt;= max_sqrt; i++) {
    if (list[i])
        for (int j = i*i; j &lt;= max; j += i)
            list[j] = false;
}


Unused Variables

The iteration variable doesn't appear to be used anywhere. It should be removed.

Error Handling

I find your error handling a little odd. (Although it's great that you have it! It's often missed. Nice work.) You check to see if there's no number, and if so, output an error and exit. But if there is a number but it's out of range, you use the maximum allowed value and continue on. I'd make them both do the same thing. Either both exit or both use the maximum and continue on. (Personally, I think stopping is smarter.)