Unable to compile C++ code

I wrote this simple c++ code trying to solve project euler problem 3.
But it does not compiles.
With GNU GCC, compiler just hangs and neither produces any error nor ends compiling, while Clang produces some strange error messages.
||=== Build: Debug in Euler3 (compiler: LLVM Clang Compiler) ===|
/home/user/Documents/Programs/C++/ProjectEuler/Euler3/main.cpp|18|current parser token 'void'|
/home/user/Documents/Programs/C++/ProjectEuler/Euler3/main.cpp|7|LLVM IR generation of declaration 'main'|
/home/user/Documents/Programs/C++/ProjectEuler/Euler3/main.cpp|7|Generating code for declaration 'main'|
||error: unable to execute command: Aborted|
||error: clang frontend command failed due to signal (use -v to see invocation)|
||note: diagnostic msg: PLEASE submit a bug report to http://llvm.org/bugs/ and include the crash backtrace, preprocessed source, and associated run script.|
||note: diagnostic msg: |
||note: diagnostic msg: /tmp/main-a90698.cpp|
||note: diagnostic msg: /tmp/main-a90698.sh|
||note: diagnostic msg: |
||=== Build failed: 5 error(s), 0 warning(s) (0 minute(s), 0 second(s)) ===|

Code:

---

#include <iostream>

using namespace std;

void sieve(bool [], long int N);

int main()
{
    const long int N = 600851475143L;
    bool primes[N] = {false};
    sieve(primes, N);
    long i;
    for(i = N / 2 + 1; !(primes[i] && N % i == 0) ; --i );
    cout<<i<<endl;
    return 0;
}

void sieve(bool primes[], long int N)
{
    for(long int i = 2; i<N; ++i)
    {
        if(!primes[i])
        {
            primes[i] = true;
            for(long int j = i * i; j<N ; j += i)
                primes[j] = true;
        }
    }
}

---

Code:

---

const long int N = 600851475143L;

---

The number is too large for a type long int (32 bit). You either need to use a smaller number or use type long long int (64 bit). Also use unsigned rather than signed int which gives a larger maximum value. The maximum value for an unsigned long int is 4294967295 (32 bit). The maximum value for an unsigned long long is 18446744073709551615 (64 bit).

Code:

---

const long long unsigned int N = 600851475143ULL;

---

and change the other long int types accordingly.

Also note that there is a limit to the size of an array - 2147483647 bytes with VS2017. So as VS2017 uses 1 byte for a bool, the maximum size of an array - and hence N - is 2147482647. (I only use VS so can't comment re these numbers for clang or gcc but they'll be similar).

So the biggest N is probably

Code:

---

const long unsigned int N = 2147482647UL;

---

If you want to use really big numbers you will probably have to allocate memory for the primes array dynamically.

When I run:

Code:

---

#include <iostream>
#include <limits>

using namespace std;

int main()
{
    cout<<"Max int: "<<numeric_limits<int>::max()<<endl;
    cout<<"Max long: "<<numeric_limits<long>::max()<<endl;
    cout<<"Max long long: "<<numeric_limits<long long>::max()<<endl;
    return 0;
}

---

Output is:

Max int: 2147483647
Max long: 9223372036854775807
Max long long: 9223372036854775807

I am on Linux Mint 18.2 64bit.

long value is well under the limit on my system.
But the size of the array might be an issue though.

Quote:

---

Originally Posted by JohnnyTest

With GNU GCC, compiler just hangs and neither produces any error nor ends compiling, while Clang produces some strange error messages.

---

you're allocating an array of billions bools on the stack ! your compiler is trying to optimize given the known array bounds, probably going out of memory during the process. Note that even if it compiled, it would have crashed immediately due to stack overflow...

Quote:

---

Originally Posted by JohnnyTest

But the size of the array might be an issue though.

---

The compiler most likely will allocate one byte per boolean. With the current N it means the array will be approximately 600 GByte.

You could reduce this by a factor 8 by instead storing 8 boolean per byte. That would mean an array size in the order of 100 GByte. If you have that much main memory you could use an std::bitset rather than an array. It allocates memory dynamically and packs 8 boolean (or rather bits but a bit is just another way of representing a boolean) per byte. If the bitset doesn't fit in memory you must lower N until it does.

But there is another issue. Your algorithm has quadratic complexity (O(N*N)). With the huge N you are currently using it may take weeks for the algorithm to finish.