Verificar se um número é primo – de forma um pouco mais rápida
Imagine que há um programa para verificar se um número é primo que já está a ser usado em produção numa grande empresa. No entanto, à medida que a empresa cresce rapidamente e o número de utilizadores aumenta, o mesmo ocorre com a quantidade de pedidos ao seu código. Pedem-lhe que otimize esse programa para que fique um pouco mais rápido, permitindo à empresa lidar melhor com a chegada de tantos novos utilizadores.
A sua solução anterior, muito provavelmente, consistia em:
- Percorrer todos os números de 2 até
ne contar quantos divisores existem.
- Percorrer todos os números de 2 até
ne parar assim que encontrar um divisor.
Podemos fazer algumas pequenas melhorias para tornar o procedimento mais eficiente:
Otimização 1:
Em vez de verificar todos os números de 2 até
n, podemos primeiro verificar se n é divisível por 2 e, em seguida, testar apenas os números ímpares. Se o número não for divisível por 2, então não há necessidade de verificar os números pares maiores (4, 6, 8, 10, 12, etc.).Otimização 2:
Em vez de percorrer de 2 até
n, podemos percorrer até n/2, pois o menor divisor possível (além de 1) é 2 ⇒ não é possível encontrar divisores maiores do que n/2.É possível combinar as duas otimizações. Assim, os candidatos a divisor passarão a ser apenas os números ímpares até
n/2. Isso significa que há cerca de n/4 números a verificar, tornando o código quatro vezes mais eficiente do que uma verificação linear simples.Essas otimizações tornam o código um pouco mais rápido, mas, em termos de complexidade, o algoritmo continua a fazer uma pesquisa linear pelos divisores. Portanto, à medida que
n cresce, o programa continua a realizar proporcionalmente mais operações. Mais à frente, discutiremos como otimizar drasticamente a verificação de primalidade para que não aumente o trabalho de forma proporcional ao aumento de n.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).Saída
O programa deve imprimir
Yes se n for primo e No caso contrário.Exemplos
Entrada | Saída |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB