Сито Эратосфена

Question

Я прочитал о сите Эратосфена, решая вопрос по Project Euler .Я уверен, что вы, ребята, знаете, о каком вопросе я говорю.Так вот в чем дело.Мой код удачно показывает все простые числа до 1 миллиона.Однако, когда я пробую ту же реализацию для 2 миллионов, это вызывает ошибку сегментации ... У меня есть определенное представление о том, почему возникает ошибка, но я не знаю, как ее исправить ... Вот код для простых чисел до 1 миллиона.

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

Answer 1

Вы выделяете огромный массив в стеке:

int prime[2000000]={};

Четыре байта, умноженные на два миллиона, равны восьми мегабайтам, что часто является максимальным размером стека. Выделение большего количества приводит к ошибке сегментации.

Вы должны разместить массив в куче, вместо этого:

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

Answer 2

Здесь была моя реализация (Java) гораздо проще, потому что вам действительно нужен только один массив, просто начните с циклов в 2.

edit: решение @cheesehead, вероятно, было лучше, я просто прочитал описание сита и подумал, что это будет хорошее упражнение на мысль.

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

Answer 3

Вот моя реализация.

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

Я протестировал его для первых 1 000 000 000 номеров на i5 Kaby Lake.

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

Я просто перевел этот псевдокод из Википедии.