Является ли этот простой генератор неэффективным C++?

Question

Это рассматривается как эффективный генератор простых чисел. Мне кажется, что это довольно эффективно. Используется ли поток, который замедляет работу программы?

Я пытаюсь представить это SPOJ и он говорит мне, что мой предел времени превышен ...

#include <iostream> 
#include <sstream> 

using namespace std; 

int main() { 
    int testCases, first, second, counter = 0; 
    bool isPrime = true; 
    stringstream out; 

    cin >> testCases; 

    for (int i = 0; i < testCases; i++) { 
     // get the next two numbers 
     cin >> first >> second; 

     if (first%2 == 0) 
      first++; 

     // find the prime numbers between the two given numbers 
     for (int j = first; j <= second; j+=2) { 
      // go through and check if j is prime 
      for (int k = 2; k < j; k++) { 
       if (j%k == 0) { 
        isPrime = false; 
        break; 
       } 
      } 
      if (isPrime) { 
       out << j << "\n"; 
      } 
      isPrime = true; 
     } 
     out << "\n"; 
    } 

    cout << out.str(); 

    return 0; 
} 

EDIT: Программа должна генерировать простые числа между числами, указанными в поле ввода. (Смотрите здесь для более подробной информации: Prime Generator Problem)

-Tomek

Answer 1

Это один шаг (пропуская четные числа) над наивным алгоритма. Я бы предложил Sieve Of Eratosthenes как более эффективный алгоритм. Из приведенной выше ссылке:

Сложность алгоритма является O ((NlogN) (loglogn)) с памятью требование O (N). В сегментированной версии решетки Эратосфена с базовыми оптимизациями, такими как факторизация колес , используются операции O (n) и O (n1/2loglogn/logn) бит .

Алгоритм, который вы даете, находится где-то рядом с O (n^2). Ускорение, которое вы получаете, пропуская evens, не так уж велико, потому что вы найдете четное число, чтобы не быть простым в первом тесте. Сито имеет гораздо большую потребность в памяти, но сложность во время выполнения намного выше для больших N.

Answer 2

Вы ищете номер больше номеров, чем вам нужно - вам нужно всего лишь перейти на <= (sqrt(num)).

Answer 3

Это может быть сделано несколько более эффективно. Вам не нужно начинать k с 2, вы уже не проверяете четные числа. Итак, начните k на 3.
Затем увеличивайте k на 2 каждый раз, потому что вам не нужно тестировать другие четные числа. Самый эффективный способ, который я могу придумать, - проверить только если число делится на известные простые числа (тогда, когда вы найдете другое, добавьте это в список, который вы тестируете).

Answer 4

for (int k = 2; k < j; k++) { 
    if (j%k == 0) { 
     isPrime = false; 
     break; 
    } 
} 

должно быть:

for(int k = 3; k <= j/2; k+=2) 
{ 
    if(j % k == 0) 
     break; 
} 

J/2 действительно следует SQRT (к), но это, как правило, достаточно хорошая оценка.

Answer 5

Вот простое сито из эратосфенов. Это не требует предварительного определения большого булевского массива, но по-прежнему остается O (n) во времени и пространстве. Тем не менее, если у вас достаточно памяти, это должно быть заметно быстрее, чем ваш настоящий наивный метод.

#include <iostream> 
#include <map> 

using namespace std; 

template<typename T = int, typename M = map<T, T> > 
class prime_iterator { 
    public: 
     prime_iterator() : current(2), skips() { skips[4] = 2; } 
     T operator*() { return current; } 
     prime_iterator &operator++() { 
      typename M::iterator i; 
      while ((i = skips.find(++current)) != skips.end()) { 
       T skip = i->second, next = current + skip; 
       skips.erase(i); 
       for (typename M::iterator j = skips.find(next); 
         j != skips.end(); j = skips.find(next += skip)) {} 
       skips[next] = skip; 
      } 
      skips[current * current] = current; 
      return *this; 
     } 
    private: 
     T current; 
     M skips; 
}; 

int main() { 
    prime_iterator<int> primes; 
    for (; *primes < 1000; ++primes) 
     cout << *primes << endl; 
    return 0; 
} 

Если это все еще слишком медленно для вас, вы можете продолжать Sieve of Atkin, оптимизированный Решето Эратосфена.

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

Answer 6

И еще одна вещь, не используйте SQRT (п) в цикле:

for(int k=1;k<sqrt(n);++k) 

Если нет хорошей оптимизации, SQRT будет рассчитываться на каждой итерации.

Использование

for (int k=1;k*k < n;++k) 

Или просто

int sq = sqrt (n); 
for (int k=1;k<sq;++k)