Verificar se um número é primo - de forma rápida
Até agora, para descobrir se um número
n é primo ou não, usávamos basicamente uma pesquisa linear de divisores. Ou seja, se aumentássemos n, a quantidade de operações para verificar se n é primo cresceria proporcionalmente (com alguma constante multiplicada). Assim, se considerarmos os cenários de pior caso (todas as vezes em que o número n era de fato primo - 51, 107, etc.), nosso algoritmo fazia aproximadamente n/4 operações para checar a primalidade de n.Isso significa que, aumentando
n em 10 vezes, o algoritmo realizaria 10 vezes mais operações. Se aumentássemos n em 100 vezes, ele faria 100 vezes mais operações. Portanto, nosso algoritmo está executando de forma proporcional a n. Será que podemos verificar a primalidade de maneira mais rápida? Parece que ainda fazemos muitas verificações redundantes.A abordagem :
Imagine que o número
n tem um divisor d.Isso significa que
n é divisível por d, e tanto d quanto são inteiros. Além disso, ou d ou é menor ou igual a . Sendo assim, ao checar se um número é primo, podemos percorrer apenas até em vez de . Estamos interessados em verificar se o número é divisível por algum outro número além de 1 ou do próprio n, então só precisamos verificar o menor entre d e . Como um ou outro é menor do que , podemos interromper a verificação ao alcançar e parar nesse ponto.Isso representa uma grande melhoria! Fazer operações em vez de
n faz muita diferença. Pense em um algoritmo que levaria 10 anos (3650 dias) para concluir um cálculo. Caso fosse otimizado para realizar operações em vez de n, levaria apenas 2 meses (61 dias) para terminar.Existem algoritmos melhores para verificar se um número é primo?
Yes! You can read more about them on Algorithms for Competitive Programming. There are algorithms that grow (do more operations as
n increases) logarithmically instead of .Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).Saída
O programa deve imprimir
Yes caso n seja primo e No caso contrário.Exemplos
Input | Output |
1 | No |
11 | Yes |
353557 | Yes |
34134741 | No |
902468477 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB