¿Es este generador principal ineficiente C ++?

Question

¿Se ve esto como un generador eficiente de números primos? Me parece que esto es bastante eficiente. ¿Es el uso de la transmisión lo que hace que el programa se ejecute más lentamente?

Estoy tratando de enviar esto a SPOJ y me dice que mi límite de tiempo excedió ...

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

EDITAR: se supone que el programa genera números primos entre los números especificados en la entrada. (Consulte aquí para obtener más detalles: Problema del generador principal )

-Tomek

Answer 1

Este es un paso (omitir números pares) por encima del algoritmo ingenuo. Sugeriría el Sieve Of Eratosthenes como un algoritmo más eficiente. Desde el enlace de arriba:

  

La complejidad del algoritmo es   O ((nlogn) (loglogn)) con una memoria   requisito de O (n). El segmentado   versión del tamiz de Eratóstenes,   con optimizaciones básicas como la rueda   factorización, utiliza operaciones O (n)   y O (n1 / 2loglogn / logn) bits de   memoria.

El algoritmo que proporciona está en algún lugar cerca de O (n ^ 2). La aceleración que obtienes al saltear los eventos no es tan buena porque encontrarás un número par que no sea primo en la primera prueba. El tamiz tiene un requisito de memoria mucho mayor, pero la complejidad del tiempo de ejecución es muy superior para las grandes N .

Answer 2

Estás buscando un lote más números de los que tienes que hacer; a lo sumo, solo tienes que ir a <= (sqrt(num)).

Answer 3

Aquí hay un simple Tamiz de Eratóstenes. No requiere predeclamar una gran matriz booleana, pero sigue siendo & Gt; & Gt; O (n) en tiempo y espacio. Sin embargo, siempre y cuando tenga suficiente memoria, debería ser notablemente más rápido que su método actual <<>> 239;

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

Si esto todavía es demasiado lento para usted, es posible que desee perseguir el Sieve of Atkin , un tamiz optimizado de Eratóstenes.

En realidad, estos son solo relativamente eficientes si el rango de primos para generar comienza bajo. Si el límite inferior ya es bastante grande y el límite superior no es mucho más grande que el inferior, entonces los métodos de tamizado son un trabajo inútil y sería mejor ejecutar un prueba de primalidad .

Answer 4

Y una cosa más, no use sqrt (n) en un bucle:

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

Si no hay una buena optimización, sqrt se calculará en cada iteración.

Uso

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

O simplemente

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

Answer 5

Se puede hacer un poco más eficiente. No necesita comenzar k en 2, ya se está asegurando de no probar números pares. Entonces comience k en 3.
Luego incremente k por 2 cada vez porque no necesita probar otros números pares. La forma más eficiente que se me ocurre es probar solo si un número es divisible por números primos conocidos (luego, cuando encuentre otro, agréguelo a la lista con la que prueba).

Answer 6

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

debería ser:

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

j / 2 realmente debería ser sqrt (j) pero generalmente es una estimación lo suficientemente buena.