Prefácio
Hoje eu vi uma pergunta que fez parecer que não era difícil determinar se um número é um número privilegiado. Portanto, decidi implementá -lo.
Estrutura dom
<! Doctype html> <html lang = "en"> <head> <meta charset = "utf-8"> <title> Calcule os números primos dentro de 500 e saída </title> <meta name = "viewport" content = "width = dispositivo-width, scale inicial = 1,0, maximum escala = 1.0,, 1,0, usuário-scalty = width, scale inicial = 1,0, máximo-escala src = "http://apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"> </sCript> </ad Head> <body> <div> <input type = "text" id = "num" value = ""> <input = "button" id = "subt". value = "submite"> </div> </body> </html> <cript> $ (function () {$ ("#submit"). compósito ");}});}); </script>Como mostrado acima, usamos a função ISPrimenum (NUM) para determinar se é um número primo. Vamos implementar esta função abaixo.
Use o loop for para determinar se é um número primo
função isprimenum (num) {for (var i = 2; i <num; i ++) {if (num%i == 0) {return false;}}; retorna true;}O princípio é relativamente simples. Ao encontrar constantemente o restante com o número de destino com 2 ou mais, se você pode obter 0, isso significa que esse é um número composto e não um número primo.
Mas esse cálculo parece ser um pouco grande
Otimizar o primeiro método
É muito simples, é implementado em pouco tempo. No entanto, parece que podemos otimizá -lo. Não precisamos perseguir esse número e encontrar o restante. Só precisamos loop para metade desse número para calcular se esse número é um número primo.
função isPrimenum (num) {for (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}}; retorna true;}Após a medição real, a velocidade foi realmente melhorada, mas eu sei que a mantissa do número é par ou 5, por isso definitivamente não é um número primo, portanto, não há necessidade de calculá -lo. Vamos otimizá -lo novamente
Nenhum número calculista cujo Mantissa é par ou 5
função isPrimenum (num) {if (! isDual (num)) {return false;} para (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}}; retorna true;} função isdual (num) {var num = num = Num.substring (num.length-1, num.length); retorno lastNum%2 == 0 || lastnum%5 == 0? Falso: verdadeiro;}Através dessa otimização, podemos reduzir a quantidade de cálculo e pelo menos metade do número. (Mas a medição real melhora o desempenho, porque esses números podem ser rapidamente julgados que não são números primos)
Aqui, a função substring () descobriu que não pode ser usada em números, mas só pode ser usada em strings. Infelizmente, o número é transformado em uma corda primeiro.
Se não for um número ou processamento inteiro
O que devo fazer se as entradas do usuário não forem um número ou decimal? Eu rapidamente escrevi dois métodos para processá -lo ...
função isPrimenum (num) {if (! isnum (num)) {return false;} if (! isInteger (num)) {return false;} if (! isDual (num)) {return false;} para (var i = 2; i <num/2+1; i ++) {se (num)}; isinteger (num) {return num == ~~ num? true: false;} função isnum (num) {var num = num.ToString (); var dallNum = num.substring (num.lengthen-1, num.length); retorno lastNum%2 == 0 || lastnum%5 == 0? Falso: verdadeiro;}Duas dicas são usadas aqui, uma é arredondar o Decimal ~~ num, e a outra é converter strings em números. +num.
Por favor, leia minha postagem anterior no blog "JS fingindo habilidades para JavaScript Learning (i) por Fungleo"
Isso não melhora a eficiência, mas apenas elimina a entrada do erro de cálculo. Vamos pensar sobre isso de novo, existe alguma maneira de determinar rapidamente se não é um número primo?
Remover números que podem ser divisíveis por 3 e não calcule
função isPrimenum (num) {if (! isnum (num)) {return false;} if (! isInteger (num)) {return false;} if (num == 2 || num == 3 || num == 5) {retorna true;} if (! isdual (num)) {return;} se (! NUM/5+1; true: false;} função isnum (num) {return num == +num? true: false;} função isdual (num) {var num = num.ToString (); var dallNum = num.substring (num.lengthen-1, num.length); retorna lastNum%2 == 0 || lastnum%5 == 0? false: true;} função istree (num) {var str = num.toString (); var sum = 0; for (var i = 0; i <str.Length; i ++) {sum+=+str.substring (i, i+1);}; retorno soma%3 == 0? Falso: verdadeiro;}Aqui, primeiro transformamos o número em uma string, depois dividimos cada bit da string, adicionamos e soma e usamos o resultado e 3 para encontrar o restante e, em seguida, podemos descobrir se esse número pode ser separado por 3.
Haha, sou tão inteligente ... o desempenho real do teste não melhorou muito, mas realmente melhorou um pouco. Está um pouco deprimido
No entanto, se excluirmos o número de três divididos, não precisamos calcular metade dele. Não precisamos calcular metade dele, só precisamos calcular um terço. Além disso, também excluímos 5, então precisamos apenas calcular um quinto ...
Após ajustes rápidos, a eficiência foi bastante aprimorada !!! Eu sou poderoso ...
No entanto, dessa maneira, o código determinará que é um número composto em 2/3/5. Portanto, outra frase precisa ser adicionada.
if (num == 2 || num == 3 || num == 5) {return true;}Métodos de outras pessoas
Então eu não conseguia pensar em um método de otimização ... então pesquisei e encontrei a solução a seguir. Fiquei chocado !!!
função isPrimenum2 (num) {return!/^.? $ |^(..+?)/1+$/. teste (matriz (num+1) .Join ('1')}O método regular é usado, é realmente curto, mas eu posso entendê -lo mesmo se eu o ler !!!
Eu realmente não entendo qual é o princípio, então fiz um teste prático e descobri que minha eficiência de código é muito maior que esse código. A partir disso, podemos ver que meu método ainda é muito excelente !!
São necessários 1600 mms para o meu código imprimir todos os números primos dentro de 100000, e esse código leva 160000ms. Ou seja, meu código leva apenas um por cento do tempo.
No entanto, se alguém puder entender esse código, explique -o ...
Reabastecer
Depois de ler algumas informações relacionadas, parece que o método que usei o NUM/5 acima não é muito bom (o resultado não está errado). Existe uma maneira melhor, que é usar o Math.Sqrt (NUM) para encontrar a raiz quadrada.
Os resultados dos meus testes de código são os seguintes
Conforme mostrado na figura acima, o resultado do cálculo do meu código está completamente correto. No entanto, foram necessários 1638 milissegundos. Ainda é o caso após muitos testes.
Os resultados do teste do método da raiz quadrada são os seguintes
Como mostrado na figura acima, esse método é mais científico e mais rápido. São necessários vários testes e leva entre 1150 milissegundos a 1250 milissegundos. Comparado ao desempenho do meu código, é cerca de 25%.
Também julgo se os dígitos são pares ou 5 e se a soma pode ser dividida por 3, o que já faz muito tempo. Definitivamente, espero reduzir a quantidade de operações. Mas esses próprios códigos também têm a quantidade de operações. Vou remover todo o meu código e depois olhar para ele.
O desempenho foi melhorado novamente. Parece que todos os meus cálculos são otimizados negativamente!
Finalmente, o código é o seguinte:
função isPrimenum (num) {if (! isnum (num)) {return false;} if (! isinteger (num)) {return false;} para (var i = 2; i <= math.sqrt (num); i ++) {if (num%i = 0) {retorn;}}; retorno; true: false;} função isnum (num) {return num == +num? Verdadeiro: false;}Resumo: Foi inteiramente por causa da minha pobre aritmética que me levou a ser inteligente na frente. No entanto, praticar pequenas técnicas também é boa -_- |||
Por fim, vamos dar uma olhada em quanto tempo leva para calcular todos os números primos dentro de 1 milhão
O exposto acima é um resumo dos métodos para julgar se um número é um número primo introduzido pelo editor. Espero que seja útil para todos.