Сумма всех простых чисел до 2 миллионов - PullRequest
Новая
       3

Сумма всех простых чисел до 2 миллионов

3 голосов
/ 10 мая 2010

Я сделал программу, которая возвращает сумму всех простых чисел до 2 миллионов. Я действительно понятия не имею, что происходит с этим, я получаю 142891895587 как мой ответ, когда правильный ответ 142913828922. Кажется, что там пропущено несколько простых чисел. Я уверен, что функция getPrime работает так, как она должна. Я использовал его пару раз и работал правильно, чем. Код выглядит следующим образом: 

vector<int> getPrimes(int number);

int main()
{

    unsigned long int sum = 0;
    vector<int> primes = getPrimes(2000000);

    for(int i = 0; i < primes.size(); i++)
    {
        sum += primes[i];
    }

    cout << sum;

    return 0;
}


vector<int> getPrimes(int number)
{

    vector<bool> sieve(number+1,false);
    vector<int> primes;
    sieve[0] = true;
    sieve[1] = true;

    for(int i = 2; i <= number; i++)
    {
        if(sieve[i]==false)
        {
            primes.push_back(i);
            unsigned long int temp = i*i;
            while(temp <= number)
            {
                sieve[temp] = true;
                temp = temp + i;
            }
        }
    }
    return primes;
}

Ответы [ 5 ]

10 голосов
/ 10 мая 2010

Выражение i*i переполнено, потому что i является int.Он усекается перед присвоением temp.Чтобы избежать переполнения, приведите его: static_cast<unsigned long>( i ) * i.

Еще лучше прервать итерацию до того, как произойдет это условие: for(int i = 2; i*i <= number; i++).

Проверено исправлено.

Кстати, выВам (не) повезло, что это не приводит к появлению дополнительных простых чисел, а также пропуска некоторых: значение int подписано и может быть отрицательным при переполнении, и, согласно моему прочтению §4.7 / 2, это приведет квнутренний цикл, чтобы пропустить.

2 голосов
/ 10 мая 2010

Возможно, вы используете ограничения на тип данных: http://en.wikipedia.org/wiki/Long_integer.

1 голос
/ 10 мая 2010

Эта строка является проблемой: 

unsigned long int temp = i*i;
0 голосов
/ 10 мая 2010

Ваша платформа должна иметь длину 64 бита. Эта строка: 

unsigned long int temp = i * i;

вычисляется неправильно, потому что я объявлен как int, а результат умножения также является int (32-битным). Принудительно сделать умножение длинным: 

unsigned long int temp = (unsigned long int) i * i;

В моей системе long 32-битный, поэтому мне пришлось изменить temp и sum на unsigned long long.

0 голосов
/ 10 мая 2010

Я дам вам подсказку.Присмотритесь к начальному значению, которое вы даете temp.Какое первое значение вы исключаете из sieve?Существуют ли другие меньшие кратные i, которые также следует исключить?Какое начальное значение вы могли бы использовать, чтобы убедиться, что все правильные числа пропущены?

Существуют некоторые методы, которые вы можете использовать, чтобы понять это самостоятельно.Одним из них является попытка заставить вашу программу работать, используя нижний предел.Вместо 2 миллионов, попробуйте, скажем, 30. Он достаточно мал, чтобы вы могли быстро вычислить правильный ответ вручную и даже просмотреть свою программу на бумаге по одной строке за раз.Это позволит вам определить, где что-то начинает идти не так.

Другой вариант - использовать отладчик для построчного обхода вашей программы.Отладчики являются мощными инструментами, хотя их не всегда легко освоить.

Вместо того, чтобы использовать отладчик для отслеживания вашей программы, вы можете распечатывать сообщения по мере ее выполнения.Скажем, пусть он напечатает каждое число в результате getPrimes вместо того, чтобы просто печатать сумму.(Это еще одна причина, по которой вы хотите сначала попробовать нижний предел - чтобы не перегружать объем производства.)

...