Bdtjtk

I compiled the following short C++ code below with gcc compiler on Windows

#include <iostream>



#define MAXN 1000000009



using namespace std;



bool prime[MAXN] = {true};



int main()

{

    for (int p = 2; p * p <= MAXN; ++p)

        if (prime[p])

        {

            cout << p << "n";



            for (int i = p * p; i <= MAXN; i += p)

                prime[i] = false;

        }



    return 0;

}

The code above prints prime numbers less than 1e9 with Sieve of Eratosthenes and doesn't have any errors,
but I noticed that the compilation takes even longer time than compilation of other of my C++ programs,
it took about few minutes to finish with no error messages.
To verify, I got the same result when I compiled again.
Even weirder, after the compilation, the code did not print anything and returned an exit code of 0.
I did not understand what's happening.
What caused this strange behaviour?

First, it is not a complication (your program is not stellar, but simple) but a compilation.

On my Linux desktop (with an i5-4690s and GCC 8 under Debian/Sid) the compilation with g++ p.cc -o p.bin of your less than optimal code takes about 8.2 seconds (certainly not forever).

Why does it take that much? Because you have an initialized but huge global variable (your prime array of booleans). So the compiler has to generate a huge binary executable (of about a gigabyte, most of it being the .data segment).

If you don't initialize that global statically, but only inside your main function, by having

bool prime[MAXN];

int main() {

  prime[2] = true;

the generated executable becomes tiny -about 17Kbytes- (because now prime sits in the .bss segment) and the compilation time is about 0.45 seconds.

If you wanted to initialize all the elements in prime you should use a for loop (or perhaps some std::memset, when initializing a range of elements to the same value).

You should think more before coding. Read about prime numbers and primality tests. You don't need such a big prime array because you are looping about √ MAXN times (which is the maximal index you need), i.e. 31623 times. So you could have declared bool prime[32000]; only (and change your program to only use elements in that range).

In practice, when you need a lot of memory, you'll better use heap memory.

If coding in C++, take advantage of its standard containers.

Of course, read How to debug small programs.

BTW, your program is very inefficient. It takes about 10 seconds to run (as p.bin > /tmp/p.out with redirection to /tmp/p.out which gets 3401 lines). For comparison, the BSD primes program (in /usr/games/primes on my Debian), when run as primes 2 31608 > /tmp/pp.out, takes less than 2 milliseconds to produce exactly the same output file, so runs nearly 5000 times faster than yours.

As commented by n.m. your original program has undefined behavior (you should be scared), because the primes[MAXN] element does not exist (you have a buffer overflow) but you are wrongly using it. So replace the inner <= MAXN with < MAXN or declare bool prime[MAXN+1];