Prime Number Generator algorithm optimization I've implemented a simple program that finds all prime numbers between two integer inputs using Sieve of Eratosthenes, but the online judge is still complaining that the time limit is exceeding. Maybe I'm doing something wrong, but how can I optimize (or debug if necessary) my code?

#include &lt;iostream&gt;
#include &lt;cmath&gt;

using namespace std;

int main()
{
    int t;
    unsigned int i, j, k;
    cin &gt;&gt; t;
    int m, n;
    cin &gt;&gt; m &gt;&gt; n;
    if (n - m &lt;= 100000 &amp;&amp; m &lt;= n &amp;&amp; 1 &lt;= m &amp;&amp; n &lt;= 1000000000)
    {
        int a[n - m + 1];
        for (j = 0; j &lt; n - m + 1; ++j)
        {
            a[j] = m + j;
        }
        for (j = 2; j &lt;= sqrt (n); ++j)
        {
            for (k = 0; k &lt; n - m + 1; ++k)
            {
                if (a[k] % j == 0 &amp;&amp; a[k] != 0)
                {
                    break;
                }
            }
            for (; k &lt; n - m + 1; k = k + j)
            {
                if (a[k] != j)
                {
                    a[k] = 0;
                }
            }
        }
        if (a[0] == 1)
        {
            a[0] = 0;
        }
        for (j = 0; j &lt; n - m + 1; ++j)
        {
            if (a[j])
            {
                cout &lt;&lt; a[j] &lt;&lt; endl;
            }
        }
        cout &lt;&lt; endl;
    }
    return 0;
}
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 &gt; 10000000) || (m &gt;= n) || (m &lt; 0) || (n &gt; 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 &lt; range; ++i) { 
    etc
}



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

#include &lt;stdio.h&gt;
#define SIZE 1000000

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

static int prime_next(char *sieve, int n, size_t size)
{
    for (int i = n + 1; i &lt; (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 &lt; 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;
}