Самый быстрый способ найти все простые числа до 4 миллиардов

Question

Самый быстрый способ найти все простые числа до 4 миллиардов

Я пытаюсь напечатать каждое простое число меньше 2 ** 32. Прямо сейчас я использую вектор bool для создания сита, а затем распечатываю простые числа после создания сита. Требуется 4 минуты, чтобы распечатать простые числа до 1 миллиарда. Есть ли более быстрый способ сделать это ?? Вот мой код

#include <iostream>
#include <cstdlib>
#include <vector>
#include <math.h>

using namespace std;

int main(int argc, char **argv){
long long limit = atoll(argv[1]);
//cin >> limit;
long long sqrtlimit = sqrt(limit);

vector<bool> sieve(limit+1, false);

for(long long n = 4; n <= limit; n += 2)
sieve[n] = true;

for(long long n=3; n <= sqrtlimit; n = n+2){
if(!sieve[n]){
for(long long m = n*n; m<=limit; m=m+(2*n))
sieve[m] = true;
}
}

long long last;
for(long long i=limit; i >= 0; i--){
if(sieve[i] == false){
last = i;
break;
}
}
cout << last << endl;

for(long long i=2;i<=limit;i++)
{
if(!sieve[i])
if(i != last)
cout<<i<<",";
else
cout<<i;
}
cout<<endl;

0

algorithm c++primes sieve-of-eratosthenes

Решение

Другие решения

Это, вероятно, ускорит это немного:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main()
{
std::vector<unsigned long long> numbers;
unsigned long long maximum = 4294967296;
for (unsigned long long i = 2; i <= maximum; ++i)
{
if (numbers.empty())
{
numbers.push_back(i);
continue;
}

if (std::none_of(numbers.begin(), numbers.end(), [&](unsigned long long p)
{
return i % p == 0;
}))
{
numbers.push_back(i);
}

}

std::cout << "Primes:  " << std::endl;
std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " "));

return 0;
}

Это своего рода обратное сито Эратосфена (вместо того, чтобы начинать с каждого числа под лимитом и удалять кратные, оно начинается с 2 и игнорирует кратные до предела).

0

Вероятно, самым быстрым способом будет создание предварительно сгенерированного списка.

http://www.bigprimes.net/ имеет первые 1,4 миллиарда простых чисел, доступных для скачивания, которые должны включать каждое простое число до 30 миллиардов или около того.

Я полагаю, что загрузка двоичного файла может занять слишком много времени, если его размер составляет несколько гигабайт.

0

Вы оценили, что занимает больше всего времени? Это само сито или запись вывода?

Один быстрый способ ускорить сито — перестать беспокоиться о четных числах. Есть только одно четное число, которое является простым, и вы можете жестко закодировать его. Это сокращает размер вашего массива пополам, что очень поможет, если вы столкнетесь с ограничениями физической памяти.

vector<bool> sieve((limit+1)/2, false);
...
for(long long m = n*n/2; m<=limit/2; m=m+n)
sieve[m] = true;

Что касается самого выхода, cout общеизвестно неэффективно. Это может быть более эффективным, чтобы позвонить itoa или что-то подобное, затем используйте cout.write вывести его. Вы могли бы даже пойти в старую школу и использовать fwrite с stdout,

0

Источник

Accepted Answer

Я обсуждаю проблему генерации большого числа простых чисел на моем блог, где я нахожу сумму первого миллиарда простых чисел 11138479445180240497. Я опишу четыре различных метода:

Грубая сила, тестирование каждого числа, начиная с 2, используя пробное деление.
Генерируйте кандидатов, используя колесо 2,3,5,7, затем проверяйте первичность с помощью тестов с сильным псевдопригодностью к базам 2, 7 и 61; этот метод работает только до 2 ^ 32, что для меня было недостаточно для суммирования первого миллиарда простых чисел, но для вас будет достаточно.
Алгоритм Мелиссы О’Нил, который использует сито, встроенное в очередь с приоритетами, что довольно медленно.
Сегментированное сито Эратосфена, которое очень быстрое, но требует места для хранения как простых, так и самих сит.

4