самый быстрый метод для нахождения числа простых чисел между двумя большими числами x и y

Question

самый быстрый метод для нахождения числа простых чисел между двумя большими числами x и y

здесь х, у<= 10 ^ 12 и у-х<= 10 ^ 6

я зациклился слева направо и проверил каждое число на простое число … этот метод очень медленный, когда x и y чем-то похожи на 10 ^ 11 и 10 ^ 12 … какой быстрый подход?
я хранил все простые числа до 10 ^ 6 .. могу ли я использовать их, чтобы найти простые числа между огромными значениями, такими как 10 ^ 10-10 ^ 12?

for(i=x;i<=y;i++)
{
num=i;
if(check(num))
{
res++;
}
}

моя функция проверки

int check(long long int num)
{
long long int i;
if(num<=1)
return 0;
if(num==2)
return 1;
if(num%2==0)
return 0;
long long int sRoot = sqrt(num*1.0);
for(i=3; i<=sRoot; i+=2)
{
if(num%i==0)
return 0;
}
return 1;
}

1

c++primes sieve-of-eratosthenes

Решение

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

Этот ресурс проходит ряд основных алгоритмов поиска в повышении сложности / эффективности. Вот описание лучшего, то есть PG7.8 (вам придется переводить обратно на C ++, это не должно быть слишком сложно)

Этот алгоритм эффективно отбирает потенциальные простые числа, исключая из рассмотрения множество ранее идентифицированных простых чисел и
минимизирует количество тестов, которые должны быть выполнены для проверки
Примат каждого потенциального простого числа. Хотя эффективность выбора
потенциальные простые числа позволяют программе просеивать через больший диапазон
число в секунду, чем дольше программа работает, тем больше тестов
которые должны быть выполнены на каждом потенциальном простом
повышаться (но возрастает медленнее по сравнению с другими алгоритмами).
Вместе эти процессы приносят большую эффективность генерации простых
числа, что делает генерацию четных 10-значных проверенных простых чисел
возможно в течение разумного количества времени на ПК.

Дальнейшие наборы пропусков могут быть разработаны, чтобы исключить выбор потенциальных простых чисел, которые могут быть учтены каждым простым числом, которое уже
был идентифицирован. Хотя этот процесс является более сложным, он может быть
обобщено и сделано несколько элегантно. В то же время мы можем
продолжать исключать из множества тестовых простых чисел каждое из простых чисел
которые пропускают наборы, устраняют кратные, минимизируя количество
тесты, которые должны быть выполнены на каждом потенциальном простом.

1

Вы можете использовать алгоритм Sieve of Eratosthenes. На этой странице есть несколько ссылок на реализации на разных языках: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

0

Вот моя реализация Сита Эратхостена:

#include <string>
#include <iostream>

using namespace std;

const int k = 110000; //you can change this constant to whatever maximum int you would need to calculate
long int p[k]; //here we would store Sieve of Erathostenes from 2 to k
long int j;

void init_prime() //in here we set our array
{
for (int i = 2; i <= k; i++)
{
if (p[i] == 0)
{
j = i;
while (j <= k)
{
p[j] = i;
j = j + i;
}
}
}
/*for (int i = 2; i <= k; i++)
cout << p[i] << endl;*/ //if you uncomment this you can see the output of initialization...
}

string prime(int first, int last) //this is example of how you can use initialized array
{
string result = "";
for (int i = first; i <= last; i++)
{
if (p[i] == i)
result = result + to_str(i) + "";
}
return result;
}

int main() //I done this code some time ago for one contest, when first input was number of cases and then actual input came in so nocases means "number of cases"...
{
int nocases, first, last;
init_prime();
cin >> nocases;
for (int i = 1; i <= nocases; i++)
{
cin >> first >> last;
cout << prime(first, last);
}
return 0;
}

Вы также можете использовать Сито Эратхостен для расчета факториала. На самом деле это самая быстрая интерпретация сита, которую я смог создать в тот день (он может рассчитать сито этого диапазона менее чем за секунду)

0

Источник

Accepted Answer

Используйте сегментированное сито Эратосфена.

То есть используйте бит, установленный для хранения чисел между x а также y, представлена x как смещение и бит, установленный для [0, y-x). Затем процедите (исключите кратные) для всех простых чисел, меньших или равных квадратному корню из y, Те числа, которые остаются в наборе, являются простыми.

С y не более 10¹² Вы должны просеять с простыми числами до 10⁶, что займет меньше секунды в правильной реализации.

10