Os números primos representam um dos conceitos mais fascinantes da Matemática. A primeira pergunta que podemos fazer sobre os números primos é se haverá uma boa maneira de os encontrar. Como é que, dado um número $n$, podemos saber se $n$ é primo? Poderá um computador responder a esta pergunta de forma eficiente? A resposta não é simples, e como veremos, o método básico que todos conhecemos não pode ser aplicado de forma "eficiente" em números muito grandes. Mas haverá algum "bom" algoritmo que responda a esta questão? Neste seminário exploraremos alguns testes de primalidade conhecidos, e encontraremos várias respostas à nossa pergunta. Mas preparem-se, pois as respostas podem não ser aquilo que nós esperávamos...