Jump to content

Números Primos


Localhost
 Share

Recommended Posts

Boas pessoal,

Estava aqui a resolver um problema da usaco. Preciso agora de descobrir números primos até um certo número da maneira mais rápida possível.

Já procurei sobre alguns algoritmos e descobri o Sieve of Eratosthenes em que basicamente para cada número cortámos todos os seus multiplos até N, no entanto, quando N começa a ficar muito grande este algoritmo já é muito lento para o que quero. Também vi o Atkin's Sieve mas este também não percebi muito bem em que consiste. Alguém me pode explicar alguns algoritmos que me possam servir para este caso? Já vi alguns post que com 1*10¹⁰ o crivo de Atkin corre em 8 segundos, penso que isto já me serviria, visto que o N máximo no caso é 1*10⁸.

here since 2009

Link to comment
Share on other sites

Não me parece que tenhas sorte.

Os exercícios da usaco são escolhidos a dedo, se neste caso pede os palindromos, é para pensares como gerar palindromos (que é uma coisa muito simples, tás mesmo com preguiça de pensar 😄 ).

Mesmo que tivesses os numeros primos que queres em tempo linear O(N), coisa que não consegues, terias cerca de 10⁸ * Verificação_Palindromo que não passaria no tempo (~10⁹).

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Ontem tava a ir para a ESTG e no caminho tava e pensar num algoritmo para calcular ate n passado como argumento ou lido do teclado,e foi o seguinte: com um ciclo for que começa de 1 ate n, a cada iteração devides o numero da iteração actual por um conjunti de numeros de 1-9 e contas o numero de vezes que o resto da divisão for inteira se for menor ou igual a 2 logo numero da iteração actual é primo( x e primo sse x tiver apenas 2 devisores inteiros que são x e 1).

Vê-la se percebes, senão diz qualquer coisa. porta-te mal.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.