Почему ввод большого числа вызовет ошибку времени выполнения для этого кода для вычисления primeCounting? - PullRequest
Новая
       30

Почему ввод большого числа вызовет ошибку времени выполнения для этого кода для вычисления primeCounting?

0 голосов
/ 21 декабря 2018

Задача состоит в том, чтобы подсчитать число простых чисел ниже входного параметра N. Я тестирую этот код с различным входным числом в диапазоне от малого до большого.Это очень странно, я столкнулся с ошибкой во время выполнения, только если входное значение больше и равно 46342. Если входное значение меньше 46342, код работает без ошибок во время выполнения.

int countPrimes(int n) {
    if (n <= 2) return 0;
    vector<bool> array(n,true);
    int cnt = 0;
    for (int i = 2 ; i < n ; i++)
    {
        for (int j = i ; i * j < n ; j++)
        {

            int product = i * j;
            if (array[product])
            {
                array[product] = false;
                cnt++;
            }
        }
    }
    return n - 2 - cnt;
}

Если входное значение больше и равно 46342, я увижу «Ошибка выполнения», если входное значение меньше 46342, код работает нормально и результат верный.

Ответы [ 3 ]

0 голосов
/ 21 декабря 2018

Максимальное значение int - это 31-я степень 2, что равно 2147483648.
Квадратный корень из этого равен 46340,95, поэтому значение, с которым вы работаете (выполняя i*j), равновыше этого предела, вызывая исключение времени выполнения.

0 голосов
/ 21 декабря 2018

Как отмечалось в других ответах, OP испытывает комбинацию двух проблем: целочисленное переполнение и неограниченный доступ к вектору, обе причины неопределенного поведения.

Линия 

int product = i * j;

Объявляет переменную int, инициализированную с произведением i и j, которые имеют тип int, в кавычках https://en.cppreference.com/w/cpp/language/types

Если длина отсутствуетприсутствуют модификаторы, ширина гарантированно не менее 16 бит.Тем не менее, в 32/64 битных системах ширина почти гарантированно равна 32 битам.

Очевидно, что в системе OP int имеет 32-битную ширину, так чтозначение i больше 46341 приводит к тому, что операция 46342 * 46342 = 2147580964 переполняет диапазон представимых чисел (вероятно, INT_MAX 2147483647).

В случае переполнения поведение не определено, но в большинстве архитектургде целые числа представлены в дополнении к 2, можно получить отрицательное число, что приводит к другой причине неопределенного поведения и, возможно, к «ошибке времени выполнения», упомянутой в вопросе: 

if (array[product])   // <- 'product' can be negative
                      //  'array.at(product)' would have caught this error
{
    array[product] = false;
//…

Простой способ предотвратитьэта проблема использует тип, достаточно большой для безопасного выполнения операции, такой как: 

long long int product = static_cast<long long int>(i) * j;

Альтернативой является перезапись логики, чтобы избавиться от проблемной части: 

#include <iostream>
#include <vector>
#include <cassert>

// Counts the number of prime numbers less than or equal to 'n'
long int count_primes(long int n)
{
    if (n < 2)   
        return 0;

    // Initialize the sieve. The first two elements (0 and 1) are ignored.
    std::vector<bool> sieve(n + 1, true);

    long int count = 0;
    for (long int i = 2; i <= n; ++i)
    {
        // If a prime is found, delete all its multiples.
        if ( sieve[i] )
        {
            // Update the counter, once only.
            ++count;
            // Instead of performing a possible overflowing operation, you can
            // use a bigger type, capable of store the result, or a different logic:
            for (long int j = i + i; j <= n; j += i)
            {
                sieve[j] = false;
            }
        }
    }
    return count;
}

int main(void)
{
    // Source: https://en.wikipedia.org/wiki/Prime-counting_function
    assert(count_primes(1) == 0);
    assert(count_primes(2) == 1);
    assert(count_primes(10) == 4);
    assert(count_primes(101) == 26);
    assert(count_primes(1000) == 168);
    assert(count_primes(10000) == 1229);
    assert(count_primes(100000) == 9592);
    assert(count_primes(1000000) == 78498);

    std::cout << "So far, so good.\n";
}
0 голосов
/ 21 декабря 2018

Это: 

int product = i * j;

переполнится, и product будет равно отрицательному числу.

Затем вы попытаетесь получить доступ к array (который на самом деле является вектором,поэтому присвоение ему имени array не является хорошим выбором) с отрицательным индексом, что приведет к сбою программы.

Вам необходимо использовать типы, которые могут поддерживать большие числовые значения.Теперь вы использовали int ( C ++ Integer Limits ).Используйте unsigned int для n, i, j и product.

...