Conteúdo principal
Tempo atual:0:00Duração total:5:22

Transcrição de vídeo

recapitulando estamos checando se um número n é primo através da divisão de tep por testes aqui nós temos a raiz quadrada dn e aqui três começando três nós vamos pulando 2 a 2 até a raiz quadrada dn ea cada ponto passado vamos checando se o número é dividido porém há tempos temos tentado diminuir o número de passos que damos talvez começando mais adiante e dando passos maiores quero parar nesse ponto um pouquinho e pensar o que é o ideal nesse caso para o algoritmo ou método de divisão por tentativas qual é a possibilidade de encontrar primes se fôssemos muito criativos em nossos passos lembre se que todo o número n tem o fator 3 vamos dizer que a raiz quadrada dn aqui precisamos passar apenas pelos números pretos esse seria o melhor poderíamos fazer porque sabemos que se passarmos apenas por prêmios vamos eventualmente encontrar o fator o fator 3 ou seja o último agora a pergunta com eficiente esse método porque parece que estamos diante de uma solução perfeita neste momento se inscrever mais um novo algoritmo chamado ele primeiramente de algoritmo com crivo digamos que esse algoritmo que calcula se o número ea prima se a gente chamar esse incrível ele vai gerar uma longa lista de números primos e então teremos a nossa divisão por tentativa que poderia usar essa lista de números pretos ela então pular e apenas nos números primos até raiz quadrada dn seja qual for então qual é o problema nisso nós podemos visualizar a complexidade temporal disso ou número de passos dados no processo nem pesquisa já foi feito foi indicado no algoritmo de criminalidade e nele foi colocado um contador de passos dentro dos looks temos um passo mais mais significa passo mais um aqui e dentro deste outro lupi também é um contador de passos mais mais são operações constantes checando e marcando os outros então nós temos um contador de passos dentro dos loops e podemos dar uma olhada numa comparação aqui no canto esquerda nós temos o método de visão por tentativas no meio o algoritmo que criamos criamos o trigo para gerar os números primos até em quem na direita a proposta conclusiva para gerar inúmeros prêmios até à esquadra dn e depois fazer a divisão por tentativa nesses números pretos vamos ver o que acontece com a nossa pequena vemos que com crivo ele começa dando muitos espaços até a versão modificada mais à direita é mais devagar do que a divisão por tentativas a medida que a mostra aumente os passos concretos com mais rápidos vamos esquecer o método do meio comparar os outros dois ou seja a divisão por tentativa ea divisão com crivo até a raiz quadrada dn mais eles vão por tentativa nós podemos ver que a divisão por tentativas ela é muito mais eficiente o número de passos concretos até a raiz quadrada ele vai aumentando muito rápido então não há uma melhor em colocar um segundo passo aqui em baixo está o programa que eu usei para fazer essa comparação ele tá gravado numa explicação conquista foi programada agora você deve estar pensando no bom isso calculamos os prémios anos então o primeiro passo seria criar uma lista de números primos e guardá los numa memória tipo hd aí o algoritmo teria que rodará divisão por tentativas e saberia como passar apenas pelos prémios porque ele estaria lendo a partir dessa lista de números primos gerado talvez essa lista armazene inúmeros prêmios de até 20 digitas ou até mesmo de seis dígitos mas porque a gente não pode fazer isso o problema é a limitação de memória quando temos inúmeras listas de números a gente tem um probleminha por exemplo vamos pensar que estamos fazendo isso a mão calculamos e vemos que cinco abrigo prevemos um papel e guardamos no arquivo calculamos e vemos os 7 guardamos aqui chegamos ao 9 desculpa ao ócio e guardamos no arquivo temos um arquivo cheio de números primos pense nele como uma lista de números pretos com grande teria que se arquive se quiséssemos armazenar - com até 20 dígitos ou até números com 100 dígitos nós poderíamos aqui vai se alista no hd para entender porque isso não é possível é preciso mergulhar mais a fundo em como isso acontece essa lista de números e qual é a limitação de memória de espaço nos tempos modernos e até como isso afetará computadores no futuro