Проект Эйлера. Задача 10 на С++

Question

Очень хотелось бы узнать на конкретном примере, существует ли более оптимизированное и быстрое решение данной задачи? Задача 10 сформулирована так:

Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17. Найдите сумму всех простых чисел меньше двух миллионов.

Моё решение (уходит несколько минут):

#include <iostream>
using namespace std;

int main() {
    unsigned long long sum = 2;
    const unsigned long long limit = 2000000;
    bool check;

    for (unsigned long long i = 3; i < limit; ++i) {
        check=false;
        for (unsigned long long j = 2; j < i; ++j) {
            if (i%j==0) {
                check=true;
                break;
            }
        }

        if (!check) {
            sum+=i;
            cout<<"Prime number "<<i<<" is being processed, current sum is "<<sum<<endl;

            }
    }

    cout<<"Sum of the prime numbers below "<<limit<<" is "<<sum;
}

Answer 1

Один из самых быстрых алгоритмов поиска простого число, это через pow. Вот в этом (линк) ответе уже дан полноценный хороший пример. И вам очень повезло что он дан как-раз на CPP.

https://stackoverflow.com/a/68809428

ps: Зря не пользуетесь google, это сэкономило-бы вам кучу времени.

Добавленно спустя

Ещё вот такой способ есть

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(long long n) {
    if (n < 2) return false;
    for(long long i=2; i<=sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}


int main() {
    for (int i=0; i<2000000; i++) {
        if (isPrime(i)) {
            cout << i << " ";
        }
    }
    return 0;
}

Answer 2

Если для любого числа вычёркивать числа ему кратные, то останутся только простые. Это идея которая лежит в основе решета Эратосфена:

#include <iostream>
#include <vector>

int main() {
    const uint64_t n = 2000000;
    uint64_t sum = 0;
    std::vector<bool> sieve(n + 1, true);
    for (uint64_t i = 2; i <= n; ++i) {
        if (sieve[i]) {
            sum += i;
            for (uint64_t j = i * i; j <= n; j += i) {
                sieve[j] = false;
            }
        }
    }
    std::cout << sum << '\n';
}

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -O3 project_euler_10.cpp

$ time ./a.out 
142913828922

real  0m0.012s
user  0m0.008s
sys   0m0.000s

БЛОГ НА HUSL

Проект Эйлера. Задача 10 на С++

Ответы (2 шт):