Ускорить поиск суммы простых чисел С++

[Izobara]

//@Izobara
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
 unsigned long long n, i, j;
 unsigned long long sum=0;
cin >> n;
 bool *a = new bool [n]; // создание массива
for (i = 0; i<n; i++) // и инициализация его всеми единицами
{
   a[i] = true;
};
for (i = 2; i<n; i++) // цикл прохода по всеми массиву с первого простого числа "2"
{
  if (a[i] == true)
{
for (j = i; j<n; j+=i) // вычеркивание всех чисел кратных данному невычеркнутому
{
   a[j] = false;
}
   a[i] = true; // присваивание данному числу значение простого
}
}
 for (unsigned long long i = 2; i<n; i++)
{
  if (a[i] == true)
{
 sum+=i;
}
}
cout<<sum;
  delete [] a;
return 0;
}

Требуется, чтобы сумму чисел в районе миллиарда находило за минуту. На процессоре intel core i7. У меня на intel core 2 duo проходит где-то за 2 минуты. Update: не, за 69 секунд Хех, неплохо.
Я думаю, что это решето Эратосфена. Вроде так называется.

[_-Re@l-_]

Я думаю, что это решето Эратосфена. Вроде так называется.

Оно, родимое.
У вас оно за O(n * log(log(n))), но его можно улучшить до O(n). Читать здесь

[Izobara]

Хм, а как это засунуть в мой код? Извините, в С++ я новичок.

[Izobara]

Ну так кто знает?

[Shad0wF1rst]

Я тут скуки ради просмотрел твою программу. И смог ее оптимизировать до 34 секунд нахождения.

[Shad0wF1rst]

unsigned long long n, i,j;
    unsigned long long summ = 2;
    n = 1000000000;
    bool *a = new bool [n+1]; // создание массива
    for (i = 3; i<n-1; i+=2) {
        a[i] = true;
        a[i+1] = false;
    }

    for (i = 3; i< n; i+=2) // цикл прохода по всеми массиву с первого простого числа "2"
    {
        //ui->textEdit_3->append((QString::number(i) + "  " + QString::number(a[i])));
        if (a[i] == true) {
            for (j = i; j<n; j+=2*i) // вычеркивание всех чисел кратных данному невычеркнутому
            {
                a[j] = false;
            }
            summ += i; // присваивание данному числу значение простого
        }
    }
    delete [] a;

[waleri]

А что будет если пометить как непростые
i * 3
i * 5
i * 7
i * 11

[Shad0wF1rst]

Сообщение от waleri

А что будет если пометить как непростые
i * 3
i * 5
i * 7
i * 11

Вопрос не совсем понятен. Можно уточнить его?!

[waleri]

Я сам себя не понял
Идея была пометить заранне на хотя бы базовые множители, исходя из идеи, что много чисел будут делится на 3 или 5 или 7 и для них не надо будет пробовать. Только потом сообразил, что эти множители тоже будут простые числа, т.е. их тоже надо вычислить...

[Shad0wF1rst]

На самом деле я так пробовал, но это хорошо работает на первой сотне. А потом не работает. )))