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 <iostream>
#include <cmath>

using namespace std;

int main()
{
int t;
unsigned int i, j, k;
cin >> t;
int m, n;
cin >> m >> n;
if (n - m <= 100000 && m <= n && 1 <= m && n <= 1000000000)
{
int a[n - m + 1];
for (j = 0; j < n - m + 1; ++j)
{
a[j] = m + j;
}
for (j = 2; j <= sqrt (n); ++j)
{
for (k = 0; k < n - m + 1; ++k)
{
if (a[k] % j == 0 && a[k] != 0)
{
break;
}
}
for (; k < n - m + 1; k = k + j)
{
if (a[k] != j)
{
a[k] = 0;
}
}
}
if (a[0] == 1)
{
a[0] = 0;
}
for (j = 0; j < n - m + 1; ++j)
{
if (a[j])
{
cout << a[j] << endl;
}
}
cout << endl;
}
return 0;
}

• I don't know enough about C++ to offer any feedback on your code, but take a look through the primes tag -- there are several questions that discuss how to implement the Sieve of Eratosthenes and other prime-seeking algorithms. – toxotes Apr 4 '13 at 12:02
• This code can be made much more readable just by reducing the vertical spacing – namely, moving opening braces to the previous line and removing redundant braces. – Konrad Rudolph Apr 4 '13 at 13:09
• @KonradRudolph: I agree, and such a change is common in Javascript. However, most C++ programmers seem to prefer braces being on their own line, never omitting redundant braces. – Brian Apr 4 '13 at 13:13
• never used Java, so i'm a typical c++ programmer :) – Kudayar Pirimbaev Apr 4 '13 at 13:30

In C++ prefer not to use using namespace std;
See: https://stackoverflow.com/q/1452721/14065 and nearly every other C++ question on code review.

Prefer one line per variable.

unsigned int i, j, k;


Also try and give you variables meaningful names.

Technaiclly variable length arrays (VLA) are not part of C++ (they are an extension inherited from C99).

int a[n - m + 1];


Main is special and does not need a return

return 0;  // If not used the compiler will plant return 0


I only use a return in main when there is a possibility of a failure being reported. Your code always returns true and you can indicate that the program is not expected to fail by not using any returns.

Algorithm

A more efficient prime finding algorithm is Sieve of Eratosthenes

There are several questions already on this subject a quick search should find them.

Style

A agree with @Konrad Rudolph that the vertical spacing is a bit extreme.

Unlike @Kondrad I personally I like having all the braces {} even if they are not required as they help solve potential problems with macros (but these are rare nowadays). So there may be some compromise here.

I also like my braces horizontally aligned like you.
But this is usually a team decision and you don't get a choice (majority rule and being consistent with the code base is more important in terms of readability).

Sometime you can use a compromise:

            if (a[k] != j)
{   a[k] = 0;    // I only do this if its a single liner.
}

// Alternatively
a[k] = (a[k] != j) ? 0 : a[k];

• emm, i have solved my problem, was every time reconstructing my sieve, thanks for comments on my style of coding – Kudayar Pirimbaev Apr 4 '13 at 20:42
• i have used "using namespace std" for simplicity, otherwise i don't use it in header files but use in implementation files; haven't given meaningful names because there was pressure in the size of code; "return 0" is my personal habit as well as horizontal align of braces; but thanks, that was a very useful comment on my code – Kudayar Pirimbaev Apr 4 '13 at 20:45

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;
}

• thanks, actually, in small programs i forget about making other functions or using reasonable names to variables, now considering to change that habit – Kudayar Pirimbaev Apr 5 '13 at 7:51
• speaking about unsigned - why is it bad to iterate with unsigned int? – Kudayar Pirimbaev Apr 5 '13 at 7:51
• It is not the iteration itself, but the use of an unsigned in combination with signed numbers. This can cause unexpected errors and will cause compiler warnings if you enable the right options. See soundsoftware.ac.uk/c-pitfall-unsigned for a discussion of unsigned – William Morris Apr 5 '13 at 12:46

Have a think about what your code actually does when it tries to remove the multiples of a large prime, lets say 31263 (just guessing that it's a prime). You start at the beginning of the sieve, using trial division to check if each number is divisible by 31263. That will take on average about 15,600 attempts. But then you continue the search if that number was already removed, which will take exactly 31263 attempts. The first multiple of 31263 that wasn't yet removed is 31263^2. So there is an excellent chance that you actually divide every number in the interval by 31263, and that is absolutely killing the performance.

If you are examining numbers from m to n, and trying to remove multiples of a prime p, the first multiple is ((m - 1) / p) + 1) * p. One calculation.

And usually you make a sieve for odd numbers only - saves you 75% of the work (since you remove multiples of all numbers, including even ones, which is pointless once multiples of 2 are removed).