Creating a list of primes

[patrick k]

I was wondering if anyone could help me a little bit with a problem I encountered on Project Euler. The specific problem at hand is to find the 10,001st prime. I have implemented what I think to be a version of the Sieve of Eratosthenes. When I modify the problem slightly to find the 10th or 20th prime the code works fine. However, when I put in the larger numbers, I'm getting a segmentation error at runtime. Is this just because my computer doesn't have enough memory, or is there a fault in the code? Any help would be much appreciated.

Here's the code I have so far:

#include <stdio.h>
#define SIZE 1000001

int main()
{
    int nums[SIZE];
    int primes[10000];
    int i = 0;
    int j = 0;
    for (i = 0; i < SIZE - 1; i++)
        nums[i] = i;
    nums[1] = 0;
    for (i = 4; i <= SIZE - 1; i += 2)
        nums[i] = 0;
    for (i = 3; i < SIZE - 1; i += 2)
    {
        if( nums[i] != 0)
        {
            if (nums[i] * nums[i] > SIZE)
               break;
            for (j = nums[i] + 2; j < SIZE - 1; j += 2)
            {
                if (nums[j] % nums[i] == 0)
                   nums[j] = 0;
            }
        }
    }
    j = 0;
    for (i = 1; i < SIZE; i += 2)
    {
        if( nums[i] != 0)
        {    
            primes[j] = nums[i];
            j++;
        }
        if (j == 10000)
        {
           primes[j] = nums[i];
           break;
        }
    }
    printf("%d", primes[10000]);
    getchar();
    return 0;
}

Thanks for the help!

[abhimanipal]

I ran your code and I got the correct o/p ie 10,4743

Where are you running your code ? Is it a specialized device ?
One thing you could do is dont jump straight to 10,000 Go there exponentially you know first calculate the 2,4,8,16,32,64 and so on

[Allophyl]

The reason for your segfault is likely due to the fact that primes only has 10000 elements, ranging from primes[0] to primes[9999]. On line 38 you're trying to assign a value to primes[10000], which doesn't exist. This problem can be solved by simply changing line 7 to

int primes[10001];

[patrick k]

I'm running the program on a machine with Windows XP. Also, I still got the problem after changing line 7. The output 104,743 is indeed the correct answer (verified on Project Euler), but I would still like to get the program running. Thanks for helping.

[abhimanipal]

Did you try to go the exponential way ?

[Allophyl]

I'm running the program on a machine with Windows XP. Also, I still got the problem after changing line 7. The output 104,743 is indeed the correct answer (verified on Project Euler), but I would still like to get the program running. Thanks for helping.

It appears line 6 needs to be changed as well, to the following:

int *nums = new int[SIZE];

It seems windows doesn't like to initialize such large arrays the way you were using, but this way will work fine.

[patrick k]

The exponent thing still produces segfaults. I think it's just a problem that the arrays are too big.

[patrick k]

Also, my compiler doesn't like the change to line 6, although I'm not quite sure what it does anyway.

[abhimanipal]

What I mean try getting
the 2 prime number then
the 4 prime number then
the 8 prime number then
the 16 prime number then
the 32 prime number ....

See at which point your code fails

[abhimanipal]

It appears line 6 needs to be changed as well, to the following:

int *nums = new int[SIZE];

It seems windows doesn't like to initialize such large arrays the way you were using, but this way will work fine.

This is a C forum ..... the operator new wont work with a C compiler

[patrick k]

Upon experimenting with the size of the big array, I found that shrinking it to 200,000 elements fixes the problems. It it just Windows being less than cooperative. Thanks for all the help guys!

[patrick k]

As a note, I figured it out when the program crashed at finding prime number 2. Leaves the array size as the only option.

[Allophyl]

This is a C forum ..... the operator new wont work with a C compiler

Oops, you're right. Sorry about that. In that case, the following can be used instead:

int *nums = (int*)malloc(SIZE*sizeof(int));

Your program needs much more stack than the default allocated by your compiler. You can change stack size by giving appropriate command line option while compiling.

Otherwise, you can either make the array static i.e. make line 7

static int primes[10001];

or dynamically allot memory using malloc()

int *nums = (int*)malloc(SIZE*sizeof(int));