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

Question

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

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

#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;
}

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

-Томек

Answer 1

Это на один шаг (пропуск четных чисел) выше наивного алгоритма.Я бы предложил Сито Эратосфена как более эффективный алгоритм.По приведенной выше ссылке:

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

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

Answer 2

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

Answer 3

Вот простое Сито Эратосфена.Это не требует предварительного отображения большого логического массива, но это все равно >> 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;
}

Если это все еще слишком медленно для вас, возможно, вы захотите продолжить Сито Аткина, оптимизированное Сито Эратосфена.

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

Answer 4

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

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)

Answer 5

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

Answer 6

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 (j), но обычно это достаточно хорошая оценка.