C++: Prime Number Generator algorithm optimization

You say you have implemented a Sieve of Eratosthenes but the code doesn't do what I understand from the Wiki page. Maybe you have changed it now, as your comment to Loki's comment implies.

Here are a few extra comments to add to those from @LokiAstari

• Use of unsigned is not necessary or desirable. Just use int unless there is good reason for an unsigned (e.g. when you have a bitmap or similar)

• You repeat the expression n - m + 1 several times. Although the compiler will optimise this away, the reader has to read it each time. Best to put such an expression into a constant, e.g.:

   const int range = n - m + 1;
  

• Variables i and t are functionally unused.

• main takes argc/argv parameters. Also, it is normal not to do all the work in main, although for a small program like this that is perhaps irrelevant.

• Your initial if clause might be better inverted to avoid the indentation caused. Also note that it is easy to mistake the precedence of operators, so brackets are safer:

  if ((n - m > 10000000) || (m >= n) || (m < 0) || (n > 1000000000)) {
      // print an error
      exit(1);
  }
  

• In general it is better to use functions to aeparate parts of a program into small units that are easily tested or otherwise verified. The overhead of a function call is often zero (the compiler can optimise the call away). So some of your loops could be extracted into functions - but only if using a function is 'makes sense' (which takes experience to decide).

• The Sieve of Eratosthenes doesn't really need any division. It is probably better to compute all primes from 2 upwards and then just print the ones requested rather than trying to start at the specified minimum bound.

• Nested loops are in my opinion best avoided.

• You say you used short names to keep the program short. But even your short names are not well considered. For example, the first loop uses j as a loop variable to initialise the sieve: access to the sieve uses a[j]. The following loop uses j as a loop variable but it is never used to access the sieve - instead the inner loop uses k as a variable: if (a[k] % j == 0..... Maybe this is nit-picking but consistency is an important aspect of programming. Note also that loop variables are often best defined in the loop:

  for (int i = 0; i < range; ++i) { 
      etc
  }
  

Here is my attempt at the sieve, for what it is worth:

#include <stdio.h>
#define SIZE 1000000

static void prime_set(char *sieve, int n, size_t size)
{
    for (int i = n + n; i < (int) size; i += n) {
        sieve[i] = 1;
    }
}

static int prime_next(char *sieve, int n, size_t size)
{
    for (int i = n + 1; i < (int) size; ++i) {
        if (!sieve[i])
            return i;
    }
    return 0;
}

static void prime_print(const char *sieve, int min, int max)
{
    for (int i = min; i < max; ++i) {
        if (!sieve[i]) {
            printf("%d\n", i);
        }
    }
}

int main(int argc, char **argv)
{
    const int min = 1;
    const int max = SIZE;
    int prime = 1;
    char sieve[SIZE] = {0};

    while ((prime = prime_next(sieve, prime, SIZE)) != 0) {
        prime_set(sieve, prime, SIZE);
    }
    /* remaining zeros in sieve are primes */
    prime_print(sieve, min, max);
    return 0;
}