Я вчера читал о Сите Эратосфена и хотел его реализовать

Question

Я вчера читал о Сите Эратосфена и хотел его реализовать

Я ищу отзывы о моей реализации алгоритма. Как я могу улучшить это? Я столкнулся с проблемами при вычислении больших простых чисел> 46349 из-за переполнения целых чисел, но исправил это, используя sqrt вместо pow.

#include<iostream>
#include<math.h>
using namespace std;

int main(){
int number;
cin >> number;
const int CAP = number;
bool * prime = new bool[CAP];

for(int i = 0; i <= CAP; i++){ //sets all to true for the marking
prime[i] = true;
}

for(int i = 2; i <= number; i++){
if(i <= sqrt(number) && prime[i] == true){
for(int j = i*i; j <=number; j++){ //if %i == 0 mark false
if(j % i == 0){               //haven't tried another way
prime[j] = false;
}
}
}
}

for(int i = 2; i <= number; i++){
if(prime[i] == true){
cout << i << endl;
}
}

return 0;
}

1

c++sieve-of-eratosthenes

Решение

Другие решения

Есть несколько вещей эффективности, которые вы можете сделать, в дополнение к исправлению массива из ошибок ошибок, которые вы получите во всех ваших циклах (используйте i < длина, а не я <= длина) Например, вы можете использовать memset в массиве, чтобы установить для него все значение true.

Кроме того, ваш внутренний цикл for (с j в качестве переменной) делает дополнительные вещи, которые ему не нужны; вместо проверки, если j% i == 0 для каждого j, просто замените j ++ на j + = i, чтобы j всегда делилось на i. Меньшей оптимизацией было бы изменение границы вашего внешнего цикла (я <= sqrt (число), поэтому вам не нужен оператор if перед внутренним циклом.

0

Вы действительно можете покончить с sqrt полностью. У тебя есть:

if(i <= sqrt(number) && prime[i] == true) {

но первое условие избыточно со следующей строкой, где i*i по сравнению с number,

   for(int j = i*i; j <= number; j++) {

Так что первое становится просто

if (prime[i]) {

0

Источник

Accepted Answer

Вы получаете доступ к массиву за пределами:

bool * prime = new bool[CAP];

for(int i = 0; i <= CAP; i++)

Вы должны изменить его, чтобы использовать < вместо <=

Обратите внимание, что то же самое относится к <= в других ваших петлях тоже.

1