项目Euler #10 [C++]素数小于2000000的和

Question

提示:小于10的素数之和为2+3+5+7= 17。找到2百万以下素数之和。

代码：

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

问题:对于46998以上的值，我得到了一个分段错误。任何等于或少于46998的东西都会像预期的那样工作。关于我做错了什么或者可以改进什么，我能得到一些帮助吗？

Answer 1

事实上，没有必要定义一个列表来计算素数之和。

不过，如果要使用您的方法，那么在语句之后的函数search中

a.erase(it);

迭代器it变得无效。

你应该写

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

或者你可以写

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

注意这个，而不是这个for循环。

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

您可以使用标头std::accumulate中声明的标准算法<numeric>。

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

使用带有列表的方法，我将按照以下方式编写程序

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

程序输出是

There are 1229 prime numbers.
Their sum is 5736396