Prime factorization

[jt1250champ]

I kept getting an segmentation fault, so I think I need to decrease memory usage but I am unsure of how. I am using the Sieve of Atkins to calculate prime numbers and then testing the primes against 600851475143 (Project Euler). Here is my code so far:

#include <iostream>
#include <cmath>
using namespace std;

int main (int argc, char* argv[])
{
    //Create the various different variables required
    long long limit = 300000000000;
    int root = ceil(sqrt(limit));
    bool sieve[limit];
    int primes[(limit/2)+1];
    int insert = 2;
    primes[0] = 2;
    primes[1] = 3;
    for (int z = 0; z < limit; z++) sieve[z] = false;
    for (int x = 1; x <= root; x++)
    {
        for (int y = 1; y <= root; y++)
        {
            //Main part of Sieve of Atkin
            int n = (4*x*x)+(y*y);
            if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
            n = (3*x*x)+(y*y);
            if (n <= limit && n % 12 == 7) sieve[n] ^= true;
            n = (3*x*x)-(y*y);
            if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
        }
    }
    //Mark all multiples of squares as non-prime
    for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false;
    //Add into prime array
    for (int a = 5; a < limit; a++)
    {
        if (sieve[a])
        {
            primes[insert] = a;
            insert++;
        }
    }
    long long number = 600851475143;
    long long x;
    int y = 0;
    int answer[x];
    for(x=0;x<300500000000;x++){
        if(number % primes[x] == 0){
            answer[y] = primes[x];
            y++;
        }else{
        }
    }
    cout<<answer[y];
}




//Create the various different variables required
long long limit = 300000000000;
int root = ceil(sqrt(limit));
bool sieve[limit];
int primes[(limit/2)+1];
int insert = 2;
primes[0] = 2;
primes[1] = 3;
for (int z = 0; z < limit; z++) sieve[z] = false;
for (int x = 1; x <= root; x++)
{
    for (int y = 1; y <= root; y++)
    {
        //Main part of Sieve of Atkin
        int n = (4*x*x)+(y*y);
        if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
        n = (3*x*x)+(y*y);
        if (n <= limit && n % 12 == 7) sieve[n] ^= true;
        n = (3*x*x)-(y*y);
        if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
    }
}
//Mark all multiples of squares as non-prime
for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false;
//Add into prime array
for (int a = 5; a < limit; a++)
{
    if (sieve[a])
    {
        primes[insert] = a;
        insert++;
    }
}
long long number = 600851475143;
long long x;
int y = 0;
int answer[x];
for(x=0;x<300500000000;x++){
    if(number % primes[x] == 0){
        answer[y] = primes[x];
        y++;
    }else{
    }
}
cout<<answer[y];


}

[Moschops]

int primes[(limit/2)+1];

This is an array of 150 000 000 001 int values. If each int is four bytes, that's 600 000 000 004 bytes. That's a bit over 500 GB. I'm guessing you don't have 500 GB of memory. Similar issue with that array of bool you have.

You need an algorithm that doesn't require you to allocate more memory than you have.

[rubberman]

I wrote a prime factorization algorithm in C many years ago (in 1985) using the Sieve of Aristostenes. You can create a small (say about 10K elements) array of prime numbers (1 == prime, 0 == not), and use recursion to determine if a number is prime or not, reducing by orders of magnitude the amount of memory required - that was on a 16-bit i286 system with only 256K of RAM. See the article on Goedel numbers for more hints and information: http://en.wikipedia.org/wiki/Goedel_numbers

Also, without resorting to special code, I could handle numbers up to that supported by an 80 bit value (that supported by the 8087 chip, which I had in my system). Factorization of these required sub-second times on my old 4MhZ Compaq "portable" computer (sewing machine in size, with handle).