CODEWITHSUNDEEP
c++c++11countruntime-errorprimes
newbie
newbie

Reputation: 9

Why a big number input will generate a runtime error for this code to compute primeCounting?

The task is to count the number of primes numbers below an input parameter N. I am testing this code with different input number ranging from small to large. It is very strange, I only encountered a runtime error if the input value is larger and equal than 46342. If the input value is smaller than 46342, the code runs perfectly fine without any runtime error. 

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;
}

If the input is bigger and equal than 46342, I will see "Runtime Error ", if the input is smaller than 46342, the code runs fine and the result is correct.

Upvotes: 0

Views: 933

Answers (3)

Bob__
Bob__

Reputation: 12779

As noted in the other answers, what the OP is experiencing is the combination of two issues, integer overflow and out of bounds access of a vector, both causes of undefined behavior.

The line

int product = i * j;

Declares an int variable initialized with the product of i and j which are of type int, which, quoting https://en.cppreference.com/w/cpp/language/types

If no length modifiers are present, it's guaranteed to have a width of at least 16 bits. However, on 32/64 bit systems it is almost exclusively guaranteed to have width of at least 32 bits.

Apparently, in OP's system an int has a 32-bit width, so that a value of i greater then 46341 makes the operation 46342 * 46342 = 2147580964 overflow the range of representable numbers (INT_MAX likely beeing 2147483647).

In case of overflow, the behavior is undefined, but in most architectures, where integers are represented in 2's complement, a negative number can be obtained, which leads to the other cause of undefined behavior and probably the "Runtime error" mentioned in the question:

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

An easy way to prevent this issue is using a type big enough to safely perform the operation, like:

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

An alternative is to rewrite the logic to get rid of the troublesome part:

#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";
}

Upvotes: 0

Dominique
Dominique

Reputation: 17533

The maximum of an int is the 31th power of 2, which is equal to 2147483648.
The square root of this is 46340.95, so the value you're working with (by performing i*j) goes above that limit, causing the runtime exception.

Upvotes: 0

gsamaras
gsamaras

Reputation: 73384

This:

int product = i * j;

will overflow, making product equal to a negative number.

Then, you will attempt to access array (which is actually a vector, so naming it array is not a good choice) with a negative index, which will make your program crash.

You need to use types that can support larger numerical values. Now you used int (C++ Integer Limits). Use unsigned int for n, i, j, and product.

Upvotes: 2

Related Questions