Алгоритм сита Эратосфена не работает в больших пределах

Question

Алгоритм сита Эратосфена не работает в больших пределах

Я запрограммировал алгоритм сита Эратосфена в C ++, и он отлично работает для меньших чисел, с которыми я его тестировал. Однако, когда я использую большие числа, то есть 2 000 000 в качестве верхнего предела, программа начинает давать неправильные ответы. Кто-нибудь может уточнить почему?

Ваша помощь ценится.

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

int main() {
clock_t a, b;
a = clock();

int n = 0, k = 2000000; // n = Sum of primes, k = Upper limit
bool r[k - 2]; // r = All numbers below k and above 1 (if true, it has been marked as a non-prime)
for(int i = 0; i < k - 2; i++) // Check all numbers
if(!r[i]) { // If it hasn't been marked as a non-prime yet ...
n += i + 2; // Add the prime to the total sum (+2 because of the shift - index 0 is 2, index 1 is 3, etc.)
for(int j = 2 * i + 2; j < k - 2; j += i + 2) // Go through all multiples of the prime under the limit
r[j] = true; // Mark the multiple as a non-prime
}

b = clock();
cout << "Final Result: " << n << endl;
cout << b - a << "ms runtime achieved." << endl;
return 0;
}

РЕДАКТИРОВАТЬ: Я только что сделал некоторые отладки и обнаружил, что он работает с пределом около 400. Однако на 500 он выключен — это должно быть 21536, но это 21499

РЕДАКТИРОВАТЬ 2: Ах, я нашел две ошибки, и они, кажется, исправили проблему.

Первый был найден другими, кто ответил, и это то, что n переполнен — после создания длинного типа данных он начал работать.

Вторая, довольно лицевая ошибка, заключалась в том, что логические значения в r должны быть инициализированы. После выполнения цикла перед проверкой простых чисел, чтобы все они были ложными, получен правильный ответ. Кто-нибудь знает, почему это произошло?

-2

algorithm c++primes sieve-of-eratosthenes

Решение

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

Других решений пока нет …

Источник

Accepted Answer

Вы просто получаете целочисленное переполнение. Тип C ++ int имеет ограниченный диапазон (в 32-битной системе обычно от — (2 ^ 32) / 2 до 2 ^ 32/2 — 1, то есть обычный максимум равен 2147483647 (конкретный максимум в вашей настройке можно узнать по # в том числе <limits> заголовок и оценка std::numeric_limits<int>::max(), Даже если k меньше максимального, ваш код рано или поздно вызовет переполнение выражений n += i + 2 или же int j = 2 * i + 2,

Вам нужно будет выбрать лучший (читай: более подходящий) тип, например unsigned который не поддерживает отрицательные числа и, таким образом, может представлять числа в два раза больше, чем int, Вы также можете попробовать unsigned long или даже unsigned long long,

Также обратите внимание, что массивы переменной длины (VLA; вот что bool r[k - 2] есть) не являются стандартными C ++. Вы можете использовать std::vector вместо. Вы также не инициализировали массив false (std::vector будет делать это автоматически), что также может быть проблемой, особенно если вы говорите, что он не работает даже при k = 500.

В C ++ вы также должны использовать <ctime> вместо <time.h> (затем clock_t а также andЧасы()are defined in theстандnamespace, but since you areиспользуя namespace std`, это не будет иметь никакого значения для вас), но это более или менее вопрос стиля.

Я нашел рабочий пример в моем «архиве кода». Хотя это не основано на вашем, вы можете найти это полезным:

#include <vector>
#include <iostream>

int main()
{
typedef std::vector<bool> marked_t;
typedef marked_t::size_type number_t; // The type used for indexing marked_t.

const number_t max = 500;

static const number_t iDif = 2; // Account for the numbers 1 and 2.
marked_t marked(max - iDif);
number_t i = iDif;

while (i*i <= max) {
while (marked[i - iDif] == true)
++i;
for (number_t fac = iDif; i * fac < max; ++fac)
marked[i * fac - iDif] = true;
++i;
}

for (marked_t::size_type i = 0; i < marked.size(); ++i) {
if (!marked[i])
std::cout << i + iDif << ',';
}
}

2