Я запрограммировал алгоритм сита Эратосфена в 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 должны быть инициализированы. После выполнения цикла перед проверкой простых чисел, чтобы все они были ложными, получен правильный ответ. Кто-нибудь знает, почему это произошло?
Вы просто получаете целочисленное переполнение. Тип 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 << ',';
}
}
Других решений пока нет …