Quiz 0x02

[DQ]

== INTRO ==
0. Um problema
1. Uma discussao
2. Quem sabe a resposta, nao conta, mas pode colaborar na discussao
3. O objetivo nao eh responder e sim discutir
4: A resposta (caso conhecida) sera dada numa thread separada depois de uns dias
5. Nao se esqueca: be excellent to each other
6. Tem uma proposta de problema? Abra um quiz vc tb!

== O PROBLEMA ==
O problema final é fazer uma rotina eficiente que determine se um número de 32 bits sem sinal (0 a 4.294.967.295) é primo ou não. Para facilitar, quebrei os problemas em alguns passos:

1. Definir o que é um número primo (parece fácil, mas tem algumas questões importantes)
2. Fazer uma rotina que tenta achar um divisor (exemplo simples abaixo, pense em como otimizar)
3. Usar uma tabela que armazene os primos conhecidos (para procurar o número ou tentar achar um divisor), qual o menor tamanho que você consegue deixar esta tabela? Implemente, por exemplo, uma tabela com os primos abaixo de 1000.
4. Investigue outras formas que não sejam procurar um divisor. Dica: uma deles é testar se é um SPRP

Eu dei uma estudada nestas coisas alguns anos atrás e fiz um post no meu blog a respeito. Para não estragar a diversão, ignorem este post enquanto não tiverem feito algumas tentativas.

Busca de divisor na força bruta em C, precisa mesmo testar todos estes números?

int primo (unsigned n)
{
  unsigned div;
  if (n < 2)
    return FALSE;
  for (div = 2; div < (n-1); div++)
  {
    if ((n % div) == 0)
      return FALSE;
  }
  return TRUE;
}



PS: Minhas respostas para o Quiz 0x01 ficam para depois do Arduino Day

[Oda]

Ja que ninguem comeca, la vou eu:

1. Um numero é primo se for inteiro positivo (natural) e tiver
exatamente dois divisores distintos: o 1 e ele mesmo. Note que por
esta definicao 1 nao eh primo.

2. Como falamos no outro quiz, modulo e divisao sao operacoes
geralmente caras. Talvez seja mais barato eliminar multiplos de dois
com if(n&1==0) return false, ja resolvi 50% dos casos, o resto deixo
para vcs :D

Para a pergunta 3 do DQ, deem uma procurada em funcao de contagem de primos.

Uma divertida leitura extra para quem se interessa pelo assunto:
www.obm.org.br/export/sites/default/semana_olimpica/docs/2011/E_tengan_primos.pdf

Abs!
--
Oda
------------------------------------------------------
If you don't have time to do it right, where
are you going to find the time to do it over?
------------------------------------------------------

> --
> -... . . -..- -.-. . .-.. .-.. . -. - - --- . .- -.-. .... --- - .... . .-.
> Regras da Lista: https://garoa.net.br/wiki/Lista:LeiaAntesDeClicarNoSend
> Para mais informações sobre o Garoa Hacker Clube acesse https://garoa.net.br
> Maiores opções sobre o Google Groups, visite:
> https://groups.google.com/group/hackerspacesp
> .--. .- .-. .- -- .- .. ... .. -. ..-. --- .-. -- .- . ... .- -.-. . ... ...
> . --- .-- .. -.- ..
> Epoch 0 <=> Fundação: 1298244863 s ~ 2.408064*10^52 tP (tempos de Planck)