Se você já passou algum tempo no código de guerras, encontrando-se um número é primo é um tema comum entre uma categoria de problemas. Quando comecei a codificar, pensei em percorrer todos os números de 1 A num e verificar se era divisível foi uma ótima abordagem. No entanto, assim que aprendi sobre a notação big O, fiquei mortificado!

depois de algumas pesquisas e wiki lendo este fim de semana, encontrei uma ótima função para descobrir se um número é primo com um tempo o(n) sub-linear. A seguinte função é a solução que encontrei:

function isPrime (num) {
if (num <= 1) {
return true
} else if (num <= 3) {
return true
} else if (num%2 === 0 || num%3 === 0) {
return false
}
let i = 5
while (i*i <= num) {
if (num%i === 0 || num%(i+2) === 0) {
return false
}
i += 6
}
return true
}
  1. verifica se o número é 0, 1 ou negativo. Retornando true se o número estiver dentro desse intervalo.
  2. verifica se o número é 2 ou 3. Retornando true se o número for 2 ou 3.
  3. a última declaração if retorna que o número não é primo se for divisível por 2 ou 3.
  4. a última parte desta função é a mais complicada-o loop while! É essencialmente verificar cada número ímpar que não é divisível por 3 até que se torne maior que a raiz quadrada do num. Por exemplo, os primeiros i e i + 2 serão 5 e 7. Os próximos i e i + 2 serão 11 e 13. Não verifica 9 ou 15 porque ambos são divisíveis por 3 e teriam sido capturados na última declaração else if.
  5. Finalmente retorna true se o número não era divisível por qualquer i ou i+2 entradas porque o número é primo.

O (n)

se assumirmos que n é o número passado para o isPrime, O o(n) da minha abordagem inicial seria o(n). Portanto, essa complexidade de tempo seria linear. Isso é bom se tudo o que você está fazendo é a verificação, mas muitas vezes esta função é uma função auxiliar e verificar se uma lista de números é primo seria exponencial.

a função acima isPrime seria O (n^1/2). Isso significa que a complexidade do tempo será sub-linear, o que diminuirá muito a complexidade do tempo de uma função maior.

Em Conclusão