É este o gerador primo ineficiente C ++?

Question

É este visto como um em eficiente gerador de número primo. Parece-me que este é bastante eficiente. É o uso do fluxo que faz com que a execução do programa mais lento?

Eu estou tentando apresentá-lo SPOJ e ele me diz que o meu limite de tempo excedido ...

#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: O programa é suposto para gerar números primos entre os números especificados na entrada. (Veja aqui para mais detalhes: Generator Primeiro Problema )

-Tomek

Answer 1

Este é um passo (ignorando até mesmo números) acima do algoritmo ingênuo. Gostaria de sugerir a Crivo de Eratóstenes como um algoritmo mais eficiente. A partir do link acima:

A complexidade do algoritmo é O ((nlogn) (loglogn)) com uma memória exigência de O (n). o segmentado versão da peneira de Eratóstenes, com as optimizações básicos, tais como rodas fatoração, utiliza operações (n) ó e S (n1 / 2loglogn / log n) bits de memória.

O algoritmo que você dá é em algum lugar perto de O (n ^ 2). O aumento de velocidade que você começa saltando nivela não é tão grande porque você iria encontrar um número ainda não ser privilegiada no primeiro teste. A peneira tem uma exigência de memória maior muito, mas a complexidade de tempo de execução é muito superior para grandes N .

Answer 2

Você está vendo um muito mais números do que você precisa -., No máximo, você só precisa ir para <= (sqrt(num))

Answer 3

Aqui está uma simples Crivo de Eratóstenes. Ele não requer predeclaring uma matriz booleana grande, mas ainda é >> O (n) no tempo e no espaço. Contanto que você tem memória suficiente, no entanto, ele deve ser visivelmente mais rápido do que o seu método naïve presente.

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

Se isso ainda é muito lento para você, você pode querer seguir o Crivo de Atkin , uma peneira otimizada de Eratóstenes.

Na verdade, estes são apenas relativamente eficiente se o intervalo de números primos para gerar começa baixa. Se o limite inferior é já bastante grande e o limite superior não é muito maior do que o inferior, em seguida, os métodos de peneiração são trabalho desperdício e você seria melhor fora de execução de um teste de primalidade .

Answer 4

E mais uma coisa, não use sqrt (n) em um loop:

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

Se não há nenhuma boa otimização, sqrt será calculado em cada iteração.

Use

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

Ou simplesmente

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

Answer 5

Pode ser feito um pouco mais eficiente. Você não precisa começar k a 2, você já está tomando cuidado para não testar mesmo números. Então comece k em 3.
Então incremento k por 2 de cada vez, porque você não precisa testar outros números pares. A maneira mais eficiente que eu posso pensar é a única prova se um número é divisível por números primos conhecidos (então quando você encontrar um outro acrescentar que a lista que você teste com).

Answer 6

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

deve ser:

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

j / 2 realmente deve ser sqrt (j), mas é tipicamente uma estimativa boa o suficiente.