CODEWITHSUNDEEP
c++c++11primes
A.Gautam
A.Gautam

Reputation: 35

Memory error in finding prime sum

Problem: Given an even number ( greater than 2 ), return two prime numbers whose sum will be equal to given number. Solution: Using sieve of eratosthenes find all prime numbers upto given number. Then find the pair of numbers whose sum is equal to given number. Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
void primesum(int A)
{
    std::vector<bool> primes(A + 1, 1);
    std::vector<int> arr, final;
    primes[0] = 0;
    primes[1] = 0;

    for (int i = 2; i <= int(sqrt(A)); i++)
    {
        if (primes[i] == 1)
        {
            for (int j = 2; i + j <= A; j++)
            {
                primes[i * j] = 0;
            }
        }
    }
    for (int i = 0; i < primes.size(); i++)
        if (primes[i])
            arr.push_back(i);

    /* for (auto x : primes)
        std::cout << x << " ";
       std::cout << "\n"; */
    std::vector<int>::iterator it;
    for (int i = 0; i < arr.size(); i++)
    {
        it = std::find(arr.begin(), arr.end(), A - arr[i]);
        if (it != arr.end())
        {
            final.push_back(arr[i]);
            final.push_back(A - arr[i]);
            break;
        }
    }
    std::cout << final[0] << " " << final[1] << "\n";
    return;
}
int main()
{
    int x = 184;
    primesum(x);
    return 0;
}

This code is working for most of the cases except for case like when x=184. Error in this case is:

a.out: malloc.c:2394: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.
[1]    13944 abort (core dumped)  ./a.out

I'm not able to understand why this is happening and what's its solution?

Upvotes: 0

Views: 109

Answers (2)

Daniel R.
Daniel R.

Reputation: 784

With primes[i * j] = 0 you have invalid indices exceeding your vector size while finding the primes, that is the reason this code crashes. You can correct this to

for (int i = 2; i <= int(sqrt(A)); i++)
{
    if (primes[i] == 1)
    {
        for (int j = 2; i * j <= A; j++)
        {
            primes[i * j] = 0;
        }
    }
}

Upvotes: 0

3CxEZiVlQ
3CxEZiVlQ

Reputation: 38773

Let x=184. Then primes.size() is 185. The first loop iterates till i=13. 13 is the prime number. The second loop iterates till j=171. In the loop you access primes[2223]. It is a write out of bounds, causes UB. As the result you get corrupted dynamic memory and the assertion.

It looks like you did a typo in the loop condition, you wanted i * j <= A.

Upvotes: 2

Related Questions