Что такое быстрый способ найти простое число в диапазоне?

Question

У меня есть этот код, чтобы найти простые числа:

void writePrimesToFile(int begin, int end, ofstream& file) 
{ 
bool isPrime = 0; 
for (int i = begin; i < end; i = i+2) 
{ 
    isPrime = 1; 
    for (int j = 2; j<i; j++) 
     if (i % j == 0) 
     { 
      isPrime = 0; 
      break; 
     } 
    if (isPrime) 
     file << i << " \n"; 
} 
} 

Есть ли более быстрый способ сделать это? Я пробовал искать по дороге быстрее, но все ее математику, и я не понимаю, как я могу превратить ее в код.

Answer 1

Есть ли более быстрый способ сделать это?

Да. Существуют более быстрые алгоритмы тестирования примитивов.

Что такое Самый быстрый способ найти простое число в диапазоне?

Никто не знает. Если кто-то знает, то этот человек охраняет серьезную важную тайну. Никто не смог доказать, что любой из известных методов является самым быстрым способом протестировать примитивность.

---

Вы могли бы спросили: Какой самый быстрый известный способ найти простое число в диапазоне.

Ответ на этот вопрос: Это зависит. Сложность некоторых алгоритмов растет асимптотически медленнее, чем у других алгоритмов, но это не имеет значения, если входные числа малы. Существуют вероятностные методы, которые очень быстрые для некоторых чисел, но имеют проблемные случаи, когда они медленнее, чем детерминированные методы.

Ваши номера ввода малы, потому что они имеют тип int и поэтому имеют довольно ограниченный диапазон. С небольшими числами простой алгоритм может быть более быстрым, чем более сложный. Чтобы узнать, какой алгоритм является самым быстрым для вашего случая использования, вы должны проверить их.

Я рекомендую начинать с Sieve of Eratosthenes, поскольку она является асимптотически быстрее, чем наивный подход, но также легко реализовать (псевдо-код, предоставленный википедии):

Input: an integer n > 1 

Let A be an array of Boolean values, indexed by integers 2 to n, 
initially all set to true. 

for i = 2, 3, 4, ..., not exceeding √n: 
    if A[i] is true: 
    for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n : 
     A[j] := false 

Output: all i such that A[i] is true.