Algoritmo de nº primos

Assuntos Gerais
#1

Bom dia.

Sei que esse é um problema meio besta de se resolver mas gostaria de pedir um auxilio. Escrevi umm algoritmo para o SPOJ no problema de nºs primos e ele estoura no tempo de execução, quero saber se alguém tem uma idéia de deixar o algoritmo mais rápido.


#include <stdio.h>
int main()
{
	int np,i,na = 0;
	scanf("%d", &np);
    if(np < 0)
        np*=-1;
    for(i = 1;  i<=np; i++)
         if((np%i)==0)
         {
            na++;
            if(na > 2)
                break;
         }
    if(na == 2)
        puts("sim");
    else
        puts("nao");
    return 0;
}

Ja troquei printf por puts no inicio não tem entrada, o ´rograma fica esperando o usuário(no caso o proprio algoritmo de verificação do SPOj) entrar com algum dado mais ainda não é aceito.

PS: estou pedindo isso não para conseguir mandar um algoritmo melhor mas sim para ver se existe uma outra lógica que tornaria esse programa mais rápido.

GRATO

#2

Para determinar se um número é primo:

a) Você só precisa checar até a raiz quadrada aproximada dele - por exemplo, para checar se 1.000.000 é primo, você só precisa checar os primeiros 1000 números. Você obviamente pode usar Math.sqrt
b) Se o número não for par (se for par, e não for 2, obviamente não é primo), você não precisa dividir pelos números pares. Portanto, você só precisaria fazer 500 cálculos de resto e não 1000, como no caso acima.
c) Para economizar tempo, se o número não for múltiplo de 3 (exceto, é claro, pelo número 3) você também não precisaria dividir pelos múltiplos de 3. Assim você só precisaria fazer 500 - 166 = 334 cálculos de resto. Você usaria a seguinte sequencia, que é bastante fácil de gerar:

5, 7, 11, 13, 17, 19, 23, 25 …
Note que a diferença entre 5 e 7 é 2, entre 7 e 11 é 4, entre 11 e 13 é 2 de novo, entre 13 e 17 é 4 de novo, e assim por diante.

#3

Bem, há um teorema, cujo nome esqueci, que diz que um número é primo se não tem nenhum divisor menor ou igual à sua raiz quadrada.

Então seria algo assim:

1 - Valide o parâmetro, se é um retorna false, se é menos que 1 erro, etc…
2 - Obtem a raiz quadrada do parâmetro.
3 - De 2 até raiz de n +1 faca
3.1 - se o numero dado é divisivel pelo parâmetro, retorne false.
4 - retorne true

#4

Esse é o programa proposto pelo entanglement:

[code]#include <stdio.h>
#include <math.h>

int main()
{
int num=0, i, step=-1, numsqrt;
scanf("%d", &num);

num = abs(num);
if(num == 1 || num == 0)  
{  
	puts("nao");  
	return(0);  
}  

if (num > 3 && (num % 2 == 0 || num % 3 == 0)) 
{
	puts("nao");
	return 0;
}

numsqrt = (int)sqrt((double)num);
for (i = 5; i <= numsqrt; i += step ? 2 : 4, step = !step)
	if (num % i == 0) 
	{
		puts("nao");
		return 0;
	}					

puts("sim");
return 0;

}
[/code]

#5

Modifiquei alguns detalhes ali para encurtar o programa e para não calcular a raiz quadrada o tempo todo.
Também tomei o cuidado de deixar o código mais legível do que seu programa original (melhores nomes de variáveis, uso de return para evitar indentação desnecessária, etc).

#6

Obrigado entanglement, daveiga, VinyGodoy. Vou tentar resolver aqui logo posto o código. Este problema é do SPOJ, acho muito legal esses sites que tem desafios de lógica. O problema é que mandei o primeiro código para avaliação e o retorno é que estourou o tempo de execução.

#7

Coloquei o nome das variáveis assim pois achei que influenciava no desempenho do algoritmo. Vou melhorar o meu código e logo posto o resultado.

Obrigado

#8

Isso não seria válido nem conceitualmente, nem na prática. Depois de compilado, nomes de variáveis nem sequer irão existir.
Eles são traduzidos para endereços de memória.

Quando falar de performance, primeiro gere um código perfeitamente claro e inteligível.
Em seguida, procure otimizar a lógica do código:

  • Primeiro, procure estruturas de dados/algorítmos eficientes para seu problema;
  • Em seguida, tente ver se é possível eliminar o espaço de busca (foi o que fizemos aqui);
  • Só por último, faça otimizações mais agressivas (como declarar coisas como static, verificar alinhamento de memória, etc.).

Mas sempre medindo se suas modificações surtiram mesmo efeito ou não.
Estude bem o que o compilador faz por você, que tipo de otimizações ele cobre, e as que ele não cobre.

Não se deixe levar por mitos ou crenças. Os códigos já são suficientemente complicados sem você rebusca-los. :wink:

#9 

#include <stdio.h>
#include <math.h>
int main()
{
    int nPrimo, i, nStep=0, nAux = 0;
    scanf("%d", &nPrimo);
    if(nPrimo < 0)
        nPrimo*=-1;

    if(nPrimo == 2 || nPrimo == 3)
    {
         puts("sim");
         return(0);
    }

    if((nPrimo%2)==0 || (nPrimo%3)==0)              // multiplos de 2 e 3 não são primos
    {
         puts("nao");
         return(0);
    }

    if(nPrimo == 1 || nPrimo == 0)
    {
         puts("nao");
         return(0);
    }

    nAux = (int)sqrt((double)nPrimo);
    for(i = 5;  i<=nAux; i+=(nStep)?2 :4, nStep =! nStep)
    {
         if((nPrimo%i)==0)
         {
            puts("nao");
            return(0);
         }
    }
    puts("sim");

    return 0;
}

Bom agora ficou assim. O problema é que o SPOJ ainda não aceita, provavelmete por causa dos returns no meio do código.

Agradeço a todos por compartilharem essa nova forma de resolver esse problmea

VinyGodoy no seu código os números 2 e 3 são informados como não primos.

#10

Isso é em C ou C++? Se for em C, o comentário “//” só é aceito por alguns compiladores porque o “//” não faz parte do padrão até o C99. Teria de usar o /* */

Não acredito que um “return” no meio do código fosse dar problemas com o SPOJ. No máximo você teria de fazer um “fflush (stdout)” ou coisa parecida.

#11

Já corrigi lá em cima.

Verifique se pelas regras do SPOJ pode-se usar a biblioteca math. Se não puder, troque o abs pela multiplicação por -1 (como vc fez) e use a metade do número no lugar da raiz quadrada.

#12

Ta dando resposta errada, e pra todos os teste que eu fiz a resposta esta certa. Você poderia ver oq esta errado no código?

#13

Pode dar o link com o enunciado desse problema no SPOJ?

#14

Notei que você inicializou step com false, e não true.

#15

http://br.spoj.pl/problems/PRIMO/.

Obs: Eu não quero passar a impressão de chato :lol: :lol: :slight_smile: mas no seu código VinyGodoy o n° 1 ta dando como primo, eu não tenho certeza agora mas pelo que eu sei 1 não é primo.

Valew.

#16

Ué, quando postei a msg ali em cima já havia corrigido isso.

#17

Rodei esse lá e foi aceito:

[code]#include <stdio.h>
#include <math.h>

int main()
{
int num=0, i, step=-1, numsqrt;
scanf("%d", &num);

num = num &lt; 0 ? -num : num;
if(num == 1 || num == 0)  
{  
	puts(&quot;nao&quot;);  
	return(0);  
}  

if (num &gt; 3 && (num % 2 == 0 || num % 3 == 0)) 
{
	puts(&quot;nao&quot;);
	return 0;
}

numsqrt = (int)sqrt((double)num);
for (i = 5; i &lt;= numsqrt; i += step ? 2 : 4, step = !step)
	if (num % i == 0) 
	{
		puts(&quot;nao&quot;);
		return 0;
	}					

puts(&quot;sim&quot;);
return 0;

}
[/code]

#18

Esse carinha em C já deu performance bem melhor 0.03 ao invés de 0.11 do outro.

[code]#include <stdio.h>
#include <math.h>

int main()
{
int num=0, i, step=-1, numsqrt;
scanf("%d", &num);

num = num &lt; 0 ? -num : num;
if ((num &lt; 2) || (num &gt; 3 && (num % 2 == 0 || num % 3 == 0))) 
{
	puts(&quot;nao&quot;);
	return 0;
}

numsqrt = (int)sqrt((double)num);
for (i = 5; i &lt;= numsqrt; i += step ? 2 : 4, step = !step)
	if (num % i == 0) 
	{
		puts(&quot;nao&quot;);
		return 0;
	}					

puts(&quot;sim&quot;);
return 0;

}[/code]

#19

No caso do maior número primo que é menor ou igual a 2^31 - 1, que é casualmente 2^31 - 1, sua raiz quadrada é 46340. O maior primo menor que 46340 é 46337. Portanto, o pior caso (exceto, é claro, 2^31 - 1) para esse programa é o número 46337 ao quadrado, que é 2147117569. Ambos os números (2147117569 e 2147483647) poderiam ser usados pelo sistema para fazer o teste de quanto tempo iria demorar seu algoritmo para ser executado.

#20