Сито эратосфена с диапазоном

Question

Я пытаюсь сгенерировать последовательность простых чисел, начиная с N до N_Max в C++. Мой подход заключается в использовании Решета Эратосфена для создания этих простых чисел:

void runEratosthenesSieve(int upperBound) { 
     int upperBoundSquareRoot = (int)sqrt((double)upperBound); 
     bool *isComposite = new bool[upperBound + 1]; 
     memset(isComposite, 0, sizeof(bool) * (upperBound + 1)); 
     for (int m = 2; m <= upperBoundSquareRoot; m++) { 
      if (!isComposite[m]) { 
        cout << m << " "; 
        for (int k = m * m; k <= upperBound; k += m) 
         isComposite[k] = true; 
      } 
     } 
     for (int m = upperBoundSquareRoot; m <= upperBound; m++) 
      if (!isComposite[m]) 
        cout << m << " "; 
     delete [] isComposite; 
} 

Однако эта функция отходы памяти пути вычисления простых чисел от 1 до N. Есть ли функция, которая будет работать быстрее и занимает меньше памяти?

Answer 1

Все, что вам нужно сделать, это определить, являются ли значения до sqrt(N_max) главными или составными, как вы уже делаете. Затем выполните цикл от N до N_max и определите, делится ли каждое значение на найденные простые числа (между 2 и sqrt(N_max)).

Это будет лишь незначительная корректировка вашего подхода.

В сторону: вместо использования с плавающей точкой для вычисления квадратного корня (т.е. sqrt()), существуют простые алгоритмы для вычисления «целочисленное квадратный корень» (то есть присваивается значение M, найти значение R которое наибольшее целое число, такой, что R*R <= M). Легко найти с помощью вашей любимой поисковой системы. Преимущество заключается в том, что он избавляет вас от нюансов с плавающей запятой и требует преобразования обратно в целое число.