머리말
오늘 나는 숫자가 소수인지 판단하기가 어렵지 않은 것처럼 보이는 질문을 보았습니다. 따라서 나는 그것을 구현하기로 결정했습니다.
DOM 구조
<! docType html> <html lang = "en"> <head> <meta charset = "utf-8"> <title> 500 내에서 소수를 계산하고 출력 </title> <meta name = "viewport"content = "width = device-width, device-width = device-width = <script src = "http://apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"> </script> </head> <body> <div> <입력 유형 = "Id ="inf "value ="> <입력 유형 = "id ="제출 "" "" " 값 = "제출"> </div> </body> </html> <cript> $ (function () {$ ( "#제출"). on ( 'click', function () {var num = $ ( "#num"). val (); if (isprimenum (num+"is"); {num+"is composite ");}});}); </script>위에서 볼 수 있듯이 ISPRIMENUM (NUM) 함수를 사용하여 소수인지 확인합니다. 아래 에서이 기능을 구현합시다.
for 루프를 사용하여 소수인지 확인하십시오.
함수 ISPRIMENUM (num) {for (var i = 2; i <num; i ++) {if (num%i == 0) {return false;}}; return true;}원칙은 비교적 간단합니다. 2 이상의 대상 수를 가진 나머지를 지속적으로 찾으면 0을 얻을 수 있다면 소수가 아닌 복합 숫자임을 의미합니다.
그러나이 계산은 약간 큰 것 같습니다
첫 번째 방법을 최적화하십시오
매우 간단하고 잠시 동안 구현됩니다. 그러나 우리는 그것을 최적화 할 수있는 것 같습니다. 우리는이 숫자를 쫓고 나머지를 찾을 필요가 없습니다. 이 숫자가 소수인지 계산하려면이 숫자의 절반으로 반복해야합니다.
함수 ISPRIMENUM (num) {for (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}}; return true;}실제 측정 후, 속도는 실제로 크게 향상되었지만 숫자의 Mantissa는 균일하거나 5라는 것을 알고 있으므로 확실히 소수가 아니므로 계산할 필요가 없습니다. 다시 최적화합시다
Mantissa가 짝수 또는 5 인 계산 숫자가 없습니다
함수 ISPRIMENUM (num) {if (! isdual (num)) {return false;} for (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}}; return true;} 함수 isdual (num) {var num = num.tostring (); Num.SubString (Num.Length-1, Num.Length); return lastnum%2 == 0 || lastnum%5 == 0? 거짓 : 참;}이러한 최적화를 통해 계산량과 숫자의 절반 이상을 줄일 수 있습니다. (그러나 실제 측정은 성능을 향상시킵니다. 그러한 숫자는 소수가 아니라고 신속하게 판단 할 수 있기 때문입니다)
여기에서 substring () 함수는 숫자에 사용할 수 없지만 문자열에서만 사용할 수 있음을 발견했습니다. 슬프게도, 숫자는 먼저 문자열로 바뀝니다.
숫자 또는 정수 처리가 아닌 경우
사용자 입력이 숫자 나 소수점이 아닌 경우 어떻게해야합니까? 나는 그것을 처리하기 위해 두 가지 방법을 빨리 썼습니다 ...
함수 isprimenum (num) {if (! isnum (num)) {return false;} if (! isinteger (num)) {return false;} if (! isdual (num)) {return false;} for (var i = 2; i <num/2+1; i ++) {if (num%i = 0)}; isinteger (num) {return num == ~~ num? true : false;} function isnum (num) {var num = num.tostring (); var lastnum = num.substring (num.length-1, num.length); return lastnum%2 == 0 || lastnum%5 == 0? 거짓 : 참;}여기에는 두 가지 팁이 사용되며, 하나는 소수점 ~~ num을 반올림하고 다른 하나는 문자열을 숫자로 변환하는 것입니다. +num.
내 이전 블로그 게시물 "JavaScript Learning을위한 JS 척 기술 (i) by Fungleo"를 읽으십시오.
이것은 효율성을 향상시키지 않지만 계산 오류 입력 만 제거합니다. 다시 생각해 봅시다. 그것이 소수인지 여부를 신속하게 결정할 수있는 방법이 있습니까?
3으로 나눌 수있는 숫자를 제거하고 계산하지 않습니다.
함수 ISPRIMENUM (num) {if (! isnum (num)) {return false;} if (! isinteger (num)) {return false;} if (num == 2 || num == 3 || num = 5) {return true;} if (! isdual (num)) {return false; num/5+1; i ++) {if (num%i == 0) {return false;}}; return true;} 함수 isinteger (num) {return num == ~~ num? true : false;} function isnum (num) {return num == +num? true : false;} function isdual (num) {var num = num.tostring (); var lastnum = num.substring (num.length-1, num.length); return lastnum%2 == 0 || lastnum%5 == 0? false : true;} 함수 isthree (num) {var str = num.tostring (); var sum = 0; for (var i = 0; i <str.length; i ++) {sum+=+str.substring (i, i+1);}; 반환 합계%3 == 0? 거짓 : 참;}여기서 먼저 숫자를 문자열로 바꾸고 문자열의 각 비트를 나누고 추가 및 합계를 나누고 결과를 사용하여 나머지를 찾은 다음이 숫자를 3만큼 분리 할 수 있는지 확인할 수 있습니다.
하하 저는 너무 똑똑합니다 ... 실제 테스트 성능은 많이 향상되지 않았지만 실제로는 조금 향상되었습니다. 조금 우울합니다
그러나 3 차분 수를 제외하면 절반을 계산할 필요가 없습니다. 우리는 그것의 절반을 계산할 필요가 없으며, 1/3 만 계산하면됩니다. 또한 5를 제외 했으므로 1/5를 계산하면됩니다.
빠른 조정 후 효율성이 크게 향상되었습니다 !!! 나는 강력하다 ...
그러나 이러한 방식으로 코드는 2/3/5의 복합 번호라고 판단합니다. 따라서 다른 문장을 추가해야합니다.
if (num == 2 || num == 3 || num == 5) {return true;}다른 사람들의 방법
그런 다음 최적화 방법을 생각할 수 없었습니다. 그래서 다음 솔루션을 검색하고 찾았습니다. 나는 충격을 받았다 !!!
함수 ISPRIMENUM2 (num) {return!/^.?일반 방법은 사용되며 실제로는 짧지 만 읽어도 이해할 수 있습니다 !!!
나는 원칙이 무엇인지 이해하지 못하므로 실용적인 테스트를 거쳤으며 코드 효율 이이 코드보다 훨씬 높다는 것을 알았습니다. 이것으로부터 우리는 내 방법이 여전히 매우 우수하다는 것을 알 수 있습니다 !!
내 코드는 100000 내에 모든 소수를 인쇄하는 데 1600ms가 걸리며이 코드는 160000ms가 걸립니다. 즉, 내 코드는 시간의 1 % 만 소요됩니다.
그러나 누군가이 코드를 이해할 수 있다면 나에게 설명 해주세요 ...
다시 채우다
일부 관련 정보를 읽은 후 위의 NUM/5를 사용한 방법은 그리 좋지 않은 것 같습니다 (결과는 잘못되지 않습니다). Math.sqrt (Num)를 사용하여 제곱근을 찾는 더 좋은 방법이 있습니다.
내 코드 테스트 결과는 다음과 같습니다
위 그림과 같이 내 코드의 계산 결과가 완전히 정확합니다. 그러나 1638 밀리 초가 걸렸습니다. 많은 테스트 후에도 여전히 그렇습니다.
제곱근 방법의 테스트 결과는 다음과 같습니다.
위 그림에서 볼 수 있듯이이 방법은 더 과학적이고 빠릅니다. 여러 번의 테스트가 필요하며 1150 밀리 초에서 1250 밀리 초가 걸립니다. 내 코드 성능에 비해 약 25%입니다.
또한 숫자가 짝수 또는 5인지, 합계를 3으로 나눌 수 있는지 판단합니다. 나는 분명히 운영량을 줄이기를 희망합니다. 그러나 이러한 코드 자체에는 작업량도 있습니다. 모든 코드를 제거한 다음 보겠습니다.
성능이 다시 개선되었습니다. 내 모든 계산은 부정적인 최적화 된 것 같습니다!
마지막으로 코드는 다음과 같습니다.
함수 isprimenum (num) {if (! isnum (num)) {return false;} if (! isinteger (num)) {return false;} for (var i = 2; i <= math.sqrt (num); i ++) {if (num%i == 0) {return false;}; return; true : false;} function isnum (num) {return num == +num? 참 : 거짓;}요약 : 그것은 전적으로 나의 열악한 산술 때문에, 나를 앞면에서 똑똑하게 만들었습니다. 그러나 작은 기술을 연습하는 것도 좋은 -_- |||입니다
마지막으로, 백만 이내의 모든 소수를 계산하는 데 얼마나 걸리는지 살펴 보겠습니다.
위는 숫자가 편집기가 소개 한 소수인지 판단하는 방법의 요약입니다. 모든 사람에게 도움이되기를 바랍니다.