Project Euler #10 [C++] sum of primes below 2000000

Question

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?

`a.erase(it)` makes `it` invalid, you need `it = a.erase(it)` — Alan Birtles, Jul 19 '22 at 19:19
And to SamV's point, the error is due to not being an experienced C++ programmer. It is not worthwhile sacrificing time in answering random puzzle questions instead of spending the time learning proper C++ through usage of good, peer-reviewed books and materials. An experienced C++ programmer would know that the iterator is invalidated, and would not even hit this error (that has nothing to do with prime numbers). The questions at Euler, hackerrank, leetcode, and similar sites are there for the *experienced* programmer who has time to spare to answer random puzzle questions. — PaulMcKenzie, Jul 19 '22 at 19:50
I'm a math major at university minoring in computer science. I'll be honest and say I only have about 2 years of coding experience. I'm doing Project Euler because a professor recommended it to me since my field of study is math. However if the issue is due to lack of experience. What are some books or materials I can read to improve the quality of my coding ability? @PaulMcKenzie — oscarm0127, Jul 19 '22 at 20:07
I'd rather go with one large `std::vector(1000000)` and apply the [sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) to... — Aconcagua, Jul 19 '22 at 20:08
[C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list)... — Aconcagua, Jul 19 '22 at 20:09
@oscarm0127 -- I suggest using a simpler, more fool-proof computer language to use if the goal is to answer the questions at the Euler site (maybe Python or similar), until you can use C++ with little to no issues (and know it well-enough to never have to ask questions concerning the basics). Yes, even experienced programmers get the iterator invalidation bug, but they can figure it out in a minute or two. C++ is one of the most difficult languages to use properly, let alone learn about containers, iterators, iterator invalidation rules, etc. That only comes with experience using C++. — PaulMcKenzie, Jul 19 '22 at 20:35
Project Euler problems are fun and challenging, though they tend to be more number theoretic. It's not a clickbait website, is not C++ specific, and makes no promises to make you an expert anything. Most people probably solve the problems using Python. Some weird takes in the comments here, perhaps people are confusing Project Euler with Codewars or some other sites. — President James K. Polk, Jul 19 '22 at 22:40

Vlad from Moscow · Accepted Answer · 2022-07-19T20:03:51.177

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

Project Euler #10 [C++] sum of primes below 2000000

1 Answers1