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);
   }
}

Befuddle

Did you for get to change int n=1000000; to int n=2000000; – Burlingame

This does look like a possibly out of bounds array access: prime[j*prime[i]]=0. – Headstock

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. – Subrogate

If he's going to be indexing a big array, he might as well use size_t – Burlingame

Answer 1

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);

Biggers

Answer 2

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.

Devries

Answer 3

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);
         }
      }

Bahuvrihi

Answer 4

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<<" ";
  }
}

Osi

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 – Setback