Блог

Я прочитал о решете Эратосфена, решая вопрос по проекту Эйлера. Я уверен, что вы, ребята, знаете, о каком вопросе я говорю. Итак, вот в чем дело. Моему коду удается правильно отображать все простые числа до 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("%dn"prime[i]);
      }
      return(0);
   }
}
 

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

 int prime[2000000]={};
 

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

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

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

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

 #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
 

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

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

редактировать: решение @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 amp;amp; marked[k]) {
            k  ;
         }
      }

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

Простая реализация сита Эратосфена

Подход: я создал логический вектор размером n 1 (скажем, n = 9, затем от 0 до 9), который выполняется во всех местах. Теперь, для i = 2, отметьте все места, кратные 2, как false (например, 4,6 и 8 при n = 9). Для i = 3 отметьте все места, кратные 3, как false (например, 6 и 9 при n = 9). Теперь для i = 4 условие i * i<=n равно false, потому что 4 * 4 = 16> 9. Итак, теперь выведите все места, которые содержат истинное значение.

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