Sieve of Eratosthenes

Question

I read up on the sieve of Eratosthenes while solving a question on Project Euler. I'm sure you guys know which question im talking about. So here's the thing. My code manages to show all the primes under 1 million correctly. However when i try the same implementation for 2 million it's giving me a segmentation fault... I have a certain idea of why the error is coming but don't know how to correct it... Here's the code for primes under 1 million.

#include<stdio.h>
int main(void)
{
   int i,k=2;
   int j;
   int n=1000000;
   int prime[2000000]={};
   for(i=0;i<n;i++) // initializes the prime number array
   {
      prime[i]=i;
   }
   for(i=2;i<n;i++) // Implementation of the Sieve
   {
      if(prime[i]!=0)
      { 
         for(j=2;j<n;j++)
         {
            {
               prime[j*prime[i]]=0;
               if(prime[i]*j>n)
                  break;    
            }
         }
      }
   }
   for(i=0;i<n;i++) // Prints the prime numbers
      if(prime[i]!=0)
      {
         printf("%d\n"prime[i]);
      }
      return(0);
   }
}

Did you for get to change `int n=1000000;` to `int n=2000000;` — Dave, Oct 27 '11 at 19:53
This does look like a possibly out of bounds array access: `prime[j*prime[i]]=0`. — Jon, Oct 27 '11 at 19:53
Of side note, you probably should be using some other data type than `int`. Int is not guaranteed to be any particular size, other than 16 bit. As a style issue I would recommend `long` for numbers above 32k. — logancautrell, Oct 27 '11 at 20:00
If he's going to be indexing a big array, he might as well use `size_t` — Dave, Oct 27 '11 at 20:09

score 14 · Accepted Answer · answered Oct 27 '11 at 19:54

You're allocating a huge array in stack:

int prime[2000000]={};

Four bytes times two million equals eight megabytes, which is often the maximum stack size. Allocating more than that results in segmentation fault.

You should allocate the array in heap, instead:

int *prime;
prime = malloc(2000000 * sizeof(int));
if(!prime) {
    /* not enough memory */
}
/* ... use prime ... */
free(prime);

cheesehead · Answer 2 · 2019-01-04T13:58:27.420

Here is my implementation.

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

int* sieve(int n) {
  int* A = calloc(n, sizeof(int));
  for(int i = 2; i < (int) sqrt(n); i++) {
    if (!A[i]) {
      for (int j = i*i; j < n; j+=i) {
        A[j] = 1;
      }
    }
  }
  return A;
}

I benchmarked it for the first 1,000,000,000 numbers on an i5 Kaby Lake.

 time ./sieve 1000000000
./sieve 1000000000  16.21s user 1.05s system 99% cpu 17.434 total

I simply translated this pseudocode from Wikipedia.

William Warner · Answer 3 · 2019-02-14T19:19:48.347

Here was my implementation (Java) much simpler in that you really only need one array, just start for loops at 2.

edit: @cheesehead 's solution was probably better, i just read the description of the sieve and thought it would be a good thought exercise.

      // set max;
      int max = 100000000;

      // logic
      boolean[] marked = new boolean[max]; // all start as false
      for (int k = 2; k < max;) {
         for (int g = k * 2; g < max; g += k) {
            marked[g] = true;
         }
         k++;
         while (k < max && marked[k]) {
            k++;
         }
      }

      //print
      for (int k = 2; k < max; k++) {
         if (!marked[k]) {
            System.out.println(k);
         }
      }

score -1 · Answer 4 · answered May 06 '21 at 10:47

Simple implementation of Sieve of Eratosthenes

Approach: I have created a boolean vector of size n+1(say n=9 then 0 to 9)that holds true at all places. Now, for i=2 mark all the places that are multiple of 2 as false(like 4,6 and 8 when n=9). For i=3, mark all the places that are multiple of 3 as false(like 6 and 9 when n=9). Now, for i=4 condition i*i<=n is false because 4*4 =16 > 9. So, now print all the places that hold true value.

void sieve(int n)
{
vector<bool> isPrime(n+1,true);
for(int i=2;i*i<=n;i++){
    if(isPrime[i])
    {
       for(int j=2*i;j<=n;j=j+i)
           isPrime[j]=false;
     }
  }
 for(int i=2;i<=n;i++){
    if(isPrime[i])
        cout<<i<<" ";
  }
}

This answer is just a variation of the answers of cheesehead and William Warner. It does not answer the question in regard to the segmentation fault — Michael Kotzjan, May 06 '21 at 10:51

Sieve of Eratosthenes

4 Answers4

Linked