Project Euler #3 C++ Program Crash

Question

The problem states:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Here is my attempt in C++

#include <bits/stdc++.h>
using namespace std;

void ProblemThree(long long int n) {
    bool prime[n];
    memset(prime, true, sizeof(prime));
    for (int i = 2; i * i < n; i++) {
        if (prime[i]) {
            if (n % i == 0) {
                printf("d", i);
                for (int k = 2 * i; k <= n; k += i) {
                    prime[k] = false;
                }
            }
        }
    }
}

int main() {
    ProblemThree(600851475143);
}

The program unexpectedly crashes, with the compiler showing no errors. Why is that and how can I stop it from happening?

`bool prime[n];` would be a "variable length array". VLAs are *not* a standard C++ feature (although some compilers unfortunately accept them as an extension - with gcc, add `-Wvla -Werror` to your compilers commandline to be sure you don't accidentally use them). If you want a dynamic array in C++, use `std::vector`. — Jesper Juhl, Jun 15 '18 at 20:31
[Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — R Sahu, Jun 15 '18 at 20:39
And `using namespace std;` - while legal, is just a *really* bad habit. — Jesper Juhl, Jun 15 '18 at 20:39
And while we are at it, `printf("d", i);` is just plain wrong. — , Jun 15 '18 at 20:40
No errors? Visual Studio disagrees. G++ Is raising two warnings with the `-pedantic -Wall -Wextra` options, one of them hints at what's likely the cause of the crash. Turn on the warnings and either justify or resolve them (prefer resolve where possible) because warnings are the first line of defense against logic errors. — user4581301, Jun 15 '18 at 20:56
Does your computer actually have 600 gigabytes of memory? Have you set your stack to be 600 gigabytes? That is why your program is unexpectedly crashing. — Eljay, Jun 15 '18 at 21:35
And I would also observe that Project Euler problems are primarily mathematical, not programming problems. Almost all of them require mathematical insight, and cannot be solved by brute-force programming. And none of them are a good way to learn to be a programmer. — , Jun 15 '18 at 21:45
@NeilButterowrth I must disagree with you. What is wrong with the solution I provided? It ia true that some problems require and can be solved using mathematical insight but it is not true that they can't be solved with programming solutions other than bruteforce. — NiVeR, Jun 16 '18 at 06:33

NiVeR · Accepted Answer · 2018-06-15T20:35:21.923

It crashes because the array that you are attempting to allocate is too big. As you have a single number to test you don't need to store the intermediate results, you can go on and compute the prime factorization of the number and take the maximum factor.

You can compute the solution with O(1) space with the following algorithm:

long long  maxPrimeFactor(long long n)
{
    long long maxPrimeFactor = 1;
    while (n%2 == 0)
    {
        n = n/2;
        maxPrimeFactor = 2;
    }

    // n must be odd at this point.  So we can skip 
    // one element (Note i = i +2)
    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        while (n%i == 0)
        {
            maxPrimeFactor = max(maxPrimeFactor, i);
            n = n/i;
        }
    }

    if (n > 2){
        maxPrimeFactor = max(maxPrimeFactor, n);
    }

    return maxPrimeFactor;
}

Note: Code is not tested, but it should give the idea and still close to working.

That sounds probable. You dont need an array of size n. At most you need an array of size sqrt(n) as you loop condition suggests. But you dont need to store all of them either. — JamesFaix, Jun 15 '18 at 20:34
@JamesFaix Indeed, this can be solved in O(1) space complexity. — NiVeR, Jun 15 '18 at 20:36

Project Euler #3 C++ Program Crash

1 Answers1