Prompt: The sum of the primes below 10 is 2 3 5 7 = 17. Find the sum of all the primes below two million.

Code:

#include <iostream>
#include <list>

/**
 * @brief Searches for numbers that in a that can be factored by b
 * 
 * @param a list of numbers
 * @param b factorable number
 */
void search(std::list<long long>& a, long long b, std::list<long long>::iterator c);

int main() {
    std::list<long long> nums;
    long long range = 0;
    long long PrimesSum = 0;

    std::cout << "Sum all the primes up to: ";
    std::cin >> range;

    for (int i = 2; i <= range; i  ) {
       nums.push_back(i);
    }

    for (std::list<long long>::iterator it = nums.begin(); it != nums.end(); it  ) {
        search(nums,*it,it);
    }
    
    for (std::list<long long>::iterator it = nums.begin(); it != nums.end(); it  ) {
        PrimesSum =*it;
    }
    std::cout << "The sum of all primes below " << range << " is " << PrimesSum << ".\n";
}

void search(std::list<long long>& a, long long b, std::list<long long>::iterator c) {
    std::list<long long>::iterator it = c;
    while (it != a.end()) {
        if (*it % b == 0 && *it != b) {
            a.erase(it);
        }
        it  ;
    }
}

Problem: I am getting a segmentation fault for values above 46998. Anything equal to or less than 46998 will work as expected. Could I get some help as to what I'm doing wrong or what I can improve?

CodePudding user response：

In fact there is no need to define a list to calculate the sum of prime numbers.

Nevertheless if to use your approach then within the function search after the statement

a.erase(it);

the iterator it becomes invalid.

You should write

while (it != a.end()) {
    if (*it % b == 0 && *it != b) {
        it = a.erase(it);
    }
    else
    {  
        it  ;
    }
}

Or you could write

  it;
while (it != a.end()) {
    if (*it % b == 0) {
        it = a.erase(it);
    }
    else
    {  
        it  ;
    }
}

Pay attention to that instead of this for loop

for (std::list<long long>::iterator it = nums.begin(); it != nums.end(); it  ) {
    PrimesSum =*it;
}

you could use standard algorithm std::accumulate declared in the header <numeric>

PrimesSum = std::accumulate( nums.begin(), nums.end(), 0ll );

Using the approach with a list I would write the program the following way

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>

int main()
{
    unsigned int range = 10'000;

    std::list<unsigned int> primes;

    for ( unsigned int i = 1; i   < range; )
    {
        if ( std::find_if( std::begin( primes ), std::end( primes ),
             [&i] ( const auto &item ) { return  i % item  == 0; } ) ==
             std::end( primes ) )
        {
            primes.push_back( i );
        }            
    }

    auto sum = std::accumulate( std::begin( primes ), std::end( primes ), 0llu );

    std::cout << "There are " << primes.size() 
              << " prime numbers.\nTheir sum is " 
              << sum << '\n';
}

The program output is

There are 1229 prime numbers.
Their sum is 5736396