Conteúdo principal
Curso: Computer science theory > Unidade 2
Lição 6: Teste de primalidade- Introdução
- Desafio do teste de primalidade
- Divisão por tentativa
- O que é a memória do computador?
- Eficiência algorítmica
- Nível 3: Desafio
- Crivo de Eratóstenes
- Nível 4: Crivo de Eratóstenes
- Teste de primalidade com crivo
- Nível 5: Divisão por tentativa usando o crivo
- Teorema do número primo
- Espiral de densidade para os números primos
- Lacunas de números primos
- Trade-off de espaço-tempo
- Resumo (o que vem a seguir?)
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
Divisão por tentativa
Defina o problema
Precisamos construir uma máquina que possa responder sim/não a uma pergunta simples. Dado um número inteiro n, n é primo?
Vamos pensar sobre o que estaria dentro desta máquina para que ela funcione. Máquinas só conseguem seguir sequências de passos com base em alguma instrução, conhecida como algoritmo. Para aquecer, vamos descobrir qual algoritmo está dentro do seu cérebro. Responda a seguinte pergunta: o número 49 é primo?
…
Não? Como você fez isso? Provavelmente você procurou um divisor de 49 que é maior que 1 e menor que 49. Se você não decorou sua tabuada , então você naturalmente seguiu esta sequência:
- 49 é divisível por 2? NÃO
- 49 é divisível por 3? NÃO
- 49 é divisível por 4? NÃO
- 49 é divisível por 5? NÃO
- 49 é divisível por 6? NÃO
- 49 é divisível por 7? SIM
Encontramos um divisor de49 (7) que prova que 49 é um número composto.
Construindo um muro
Entretanto, e se eu perguntasse se o número 2971215073 é primo?
Você ainda está tentando? Depois dos primeiros milhares de testes, eu ainda não encontrei um divisor. A pergunta principal é, quando podemos parar de procurar e provar que o número n é primo? (vamos chamar isso de nossa parede) Como ponto de partida, sabemos que nossa parede deve ser n-1 (pois n é divisível por n). Se nós checarmos um número até 2971215072 ou nós acharemos um divisor (que provará que n é composto) ou nós não acharemos um divisor (que provará que n é primo).
Construindo um muro melhor
Isso funciona, mas podemos mover nosso muro para economizar tempo? Lembre-se que na realidade estamos procurando pelo primeiro(ou menor) divisor. Às vezes o menor divisor pode ser 2, mas também pode ser muito maior. Isso nos leva à pergunta chave: quão grande pode ser o menor divisor?
Lembre-se que qualquer inteiro composto n é formado por dois ou mais números primos n = P * P …
P é maior quando n tiverexatamente dois divisores que forem iguais entre si. Isso é conhecido como um quadrado perfeito tal como 9 (9 = 33) ou 49 (49 = 77). Para capturar este pior cenário, simplesmente construímos nosso muro na raiz quadrada de n!
Convença-se do seguinte: se nós não encontrarmos um divisor de n depois de verificar até a raiz quadrada de n, então n deve ser primo. Tente provar isso para si mesmo (a prova encontra-se na parte inferior deste artigo)
Algoritmo de divisão experimental
É isso ai, estamos prontos para prosseguir. Primeiro, vamos resumir nosso algoritmo de divisão experimental em Português claro:
- Aceite um número inteiro n
- Para cada número inteiro x de {2 ... sqrt(n)} verifique se n é divisível por x
- Se você encontrou um divisor, então n é composto .CASO CONTRÁRIO n é primo
Se você tiver experiência em programação, você deve abrir um bloco de notasCS e tentar fazer este função funcionar. Caso contrário, você pode seguir para o próximo passo onde há uma versão funcionando para usar como ponto de partida. (Observação: É possível ter esta aula sem fazer nenhuma programação).
Quer participar da conversa?
se numero pode ser dividido 7 pode ser dividido por ouro número numa calculatora científica?(1 voto)