É este o gerador primo ineficiente C ++?
-
04-07-2019 - |
Pergunta
É 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
Solução
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 .
Outras dicas
Você está vendo um muito mais números do que você precisa -., No máximo, você só precisa ir para <= (sqrt(num))
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 .
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)
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).
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.