0

So I'm trying to write a program to solve the Project Euler problem on greatest prime factor, and while I know the code is structurally correct (insofar as it return correct answers for smaller numbers, including the example 13195 that they give), I keep receiving a segmentation fault when I input the number we are supposed to solve, which is 600851475143. The code is as follows:

#include <stdio.h>
#include <math.h>

main(){
    int number,a,b,c,i,j,n,gpf;
    printf("Input number to analyze: ");
    scanf("%d",&number);
    a = number/2;
    printf("%d\n",a);
    int* primesieve = new int[a+1];               /*IMPORTANT LINE*/
    for (i=0;i<a+1;i++){
        primesieve[i] = 1;
    }
    for (j=2;j<=a;j++){
        if (primesieve[j] == 1){
            for (c=2;j*c<=a;c++){
                primesieve[j*c] = 0;
            }
        }
    }
    for (n=2;n<=a;n++){
        b = number/n;
        printf("%d\n",b);
        if (number % n == 0){
            if (primesieve[b] == 1){
                gpf = b;
                n = a+1;
            }
        }
    }
    delete[] primesieve;
    printf("The greatest prime factor of %d is %d.\n",number,gpf);
}

The problem comes from the initialization of the array for the prime sieve, because I omitted all lines after that one and still encountered the problem. I originally declared the array using the following code, which returned a segmentation fault for values as low as 10 million.

int primesieve[a+1];

I searched for a solution on this site, which yielded the change to dynamic array allocation, but while this solved the problem for 10 million, it apparently did not for significantly larger values. Other solutions I noticed mentioned something about using malloc() or declaring the array statically outside of main(), but frankly I didn't understand those as my introductory programming class barely mentioned malloc() and I thought the code leading up to the declaration of the array needed to be contained in main(). (For reference: Segmentation Fault While Creating Large Arrays in C and Seg Fault when initializing array.) I'm sure this is a fairly simple problem, but I'm a relatively new programmer and thus have a poor understanding of allocating memory, so any suggestion, solution, or explanation of the other solutions I found would be greatly appreciated.

Community
  • 1
  • 1
Arnold Myers
  • 43
  • 7
  • Okay, so both of you are saying that it's impossible to have such a large sieve on a "normal" computer? Since I'm not going to get top end computer just to answer a Project Euler question, is there a better way to approach the sieving beyond the bitmapping and omission of even numbers? Piecemeal, perhaps? Edit: I should have mentioned this above - I am on Vista 64 with 4GB, and running the program through Cygwin. – Arnold Myers Oct 19 '13 at 09:51
  • Okay, I see that the sieve is simply infeasible for this scale of number. I'll try a different approach, even if this algorithm clearly works for smaller numbers. Thank you to each of the answers that were given below. – Arnold Myers Oct 19 '13 at 10:05
  • If you intend to code C++ I would HIGHLY suggest you take a look [The book list](http://stackoverflow.com/a/388282/332733) – Mgetz Jan 22 '15 at 16:29
  • You solved it for small numbers, which is a good first step, but then they scale it up so that nobody has enough memory to brute force. And that's the whole point of project Euler. – Kenny Ostrom Jan 22 '15 at 16:34

2 Answers2

0
600851475143 * sizeof(int64_t) = 4806811801144 = 4.4TB

In other words, this code will always crash unless you have 5TB of RAM.

You can make it a bit more bearable if you use bitmap for your sieve. For example, using 1 bit per number, and not mapping even numbers only needs 600851475143 / 8 / 2 = 35GB of RAM. Still a lot, but feasible if you have some money for the hardware.

mvp
  • 111,019
  • 13
  • 122
  • 148
0

Your experience is related to the physical limits and the precision of your compiler. The first attempt, allocating the array on the stack 

int primesieve[a+1];

quickly failed, because on most systems the stack is rather limited in size compared to the heap.

Allocating on the heap 

int* primesieve = new int[a+1];

gives you more space, but you still have the limit of addressable memory. Now, 600851475143 is quite a large number, even if you divide it by 2. And assuming the size of int is 4 bytes, you might wonder, if you really can address that much memory. With 32 bits you can address 2^32 = 4294967296 bytes.

Peter Hübel
  • 196
  • 5