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

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

2 голосов
/ 24 октября 2008

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

Я пытаюсь отправить это 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;
}

РЕДАКТИРОВАТЬ: Программа должна генерировать простые числа между числами, указанными во входных данных. (Более подробную информацию см. Здесь: Проблема с генератором )

-Tomek

Ответы [ 6 ]

14 голосов
/ 24 октября 2008

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

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

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

7 голосов
/ 24 октября 2008

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

4 голосов
/ 25 октября 2008

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

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

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

3 голосов
/ 04 июля 2009

И еще одна вещь, не используйте 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)
0 голосов
/ 24 октября 2008 
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), но обычно это достаточно хорошая оценка.

0 голосов
/ 24 октября 2008

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

...