Поиск простых чисел с многопоточностью

Question

пытаюсь написать максимально быструю программу для поиска простых чисел. Пока лучший результат (он представлен в коде) находит все простые чиса до миллиона за 0,971 секунду на моем компьютере. Алгоритмически более никак результат не могу улучшить (возможно, вы знаете как, я с радостью послушаю), пришло в голову прикрутить многопоток. В питоне это можно было сделать относительно просто с помощью дополнительной библиотеки Numba. А как с этим состоят дела в C++? Просто сколько искал, не смог найти внятного объяснения. И имеет ли вообще смысл улучшать дальше или даже идеально работающий многопоток не даст никакого прироста (тогда почему?)?

P.S. Функцию вызываю три раза просто для большей точности, в качестве значений беру среднее по 3м измерениям

 #include <iostream>
 using namespace std;

void IsPrime() {

float start_time = clock(); //Засекаем время начала

int n = 10000000; //Задаем число, до которого будем перебирать.
int count = 0; //Переменная count - количество простых чисел, которорое мы получим после работы алгоритма.

for (int i = 3; i < n + 1; i+=2) { //Алгоритм перебора
    bool check = true;
    for (int j = 3; j < (int)sqrt(i)+1; j+=2) {
        if (i % j == 0) {
            check = false;
            break;
        }
    }
    if (check) {
        count++;
    }
    else {
        check = true;
    }
}

float end_time = clock(); //Засекаем время  конца
float final_time = (end_time - start_time) / 1000.0; //Считаем итоговое время
cout << "Всего простых чисел: " << count+1 << '\n' << "Времени потрачено: " << final_time << " секунд" << endl;
}

int main()
{
setlocale(LC_ALL, "RUS");

IsPrime(); //Первый замер
IsPrime(); //Второй замер
IsPrime(); //Третий замер

}

Answer 1

попробуйте воспользоватьcя тем свойством простых чисел, что любое простое число больше 3 представимо в виде 6k - 1 или 6k + 1

if (n > 10)
    count = 4;

for (int i = 5; i < n + 1; i += 6) {

    const int limit = (int)sqrt(i) + 6;

    count++;

    for (int j = 6; j < limit; j += 6) {
        if ((i % (j - 1) == 0) || (i % (j + 1) == 0)) {
            count--;
            break;
        }
    }
}

for (int i = 7; i < n + 1; i += 6) {

    const int limit = (int)sqrt(i) + 6;

    count++;

    for (int j = 6; j < limit; j += 6) {
        if ((i % (j - 1) == 0) || (i % (j + 1) == 0)) {
            count--;
            break;
        }
    }
}

Answer 2

Битовое решето Эратосфена для нечётных чисел. Это последовательный алгоритм.

Когда построены простые до миллиарда, можно применить сегментированное решето Эратосфена: числа от 10^9 до 10^18 разбить на сегменты по миллиарду. В каждом сегменте выполнять просеивание. Это уже параллельный алгоритм. Когда очередное ядро просеяло очередной сегмент его печатают и выбрасывают.

Битовая маска одного сегмента 64MB, скажем, восемь сегментов параллельно - полгига. 203 мегабайта нужно для простых до миллиарда. На всё про всё не больше гига и вы будете просеивать простые со скоростью миллиард чисел в секунду (загибаю, такая производительность будет только для первых сегментов, дальше будет медленнее). Процесс закончится через миллиард секунд (32 года) - вы дойдёте до 10^18.

Процесс можно распределить между любым количеством компьютеров. Обработка отдельных сегментов не зависит друг от друга.

Но если вы действительно решите идти этим путём, то есть ещё более эффективные алгоритмы.

#include <iostream>
#include <vector>

void print_primes(const unsigned long long n) {
    const unsigned long long n2 = n / 2;
    std::vector<bool> sieve(n2, true);
    if (2 < n) {
        std::cout << 2 << '\n';
        unsigned long long k;
        for (k = 1; ; ++k) {
            if (sieve[k]) {
                const unsigned long long i = 2 * k + 1;
                const unsigned long long i2 = i * i;
                if (i2 >= n) {
                    break;
                }
                std::cout << i << '\n';
                for (unsigned long long j = i2 / 2; j < n2; j += i) {
                    sieve[j] = false;
                }
            }
        }
        for (; k < n2; ++k) {
            if (sieve[k]) {
                std::cout << 2 * k + 1 << '\n';
            }
        }
    }
}

int main() {
    unsigned long long n;
    if (std::cin >> n) {
        print_primes(n);
    }
}

Девять секунд до миллиарда:

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -O3 sieve-of-eratosthenes.cpp

$ time echo 10000000 | ./a.out | wc -l
664579

real  0m0.073s
user  0m0.068s
sys   0m0.012s

$ time echo 100000000 | ./a.out | wc -l
5761455

real  0m0.707s
user  0m0.756s
sys   0m0.028s

$ time echo 1000000000 | ./a.out | wc -l
50847534

real  0m8.295s
user  0m8.808s
sys   0m0.304s

БЛОГ НА HUSL

Поиск простых чисел с многопоточностью

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