자바스크립트에서 소수를 찾는 방법

소수 찾는 방법: 1. 1~n 범위의 모든 자연수를 순회하여 n으로 나눕니다. 나머지가 0이면 숫자 n은 소수가 아니라는 의미이고, 그렇지 않으면 소수입니다. 구문은 "for(i=2;i

이 튜토리얼의 운영 환경: Windows 7 시스템, JavaScript 버전 1.8.5, Dell G3 컴퓨터.

소수의 개념

소수는 1보다 큰 자연수 중 1과 자기 자신을 제외한 다른 자연수로 나누어지지 않는 수를 말합니다.

100 내의 소수: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 총 25개입니다.

JavaScript에서 소수를 결정하는 네 가지 방법

1. 소수는 1과 자기 자신으로만 나누어질 수 있습니다.

소수는 1과 자기 자신으로만 나누어질 수 있으므로 (1, n) n으로 나누기 위한 열린 간격 정수 나누기가 있으면, 즉 나머지가 0이면 숫자 n은 소수가 아니라는 의미이고, 그렇지 않으면 소수입니다.

function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  for (let i = 2; i <p>하지만 이 알고리즘의 복잡도는 O(n)</p><h3 id="%E7%B4%A0%E6%95%B0%E5%B9%B3%E6%96%B9%E6%A0%B9%E8%8C%83%E5%9B%B4"><strong>2이고, 소수의 제곱근의 범위는 </strong></h3><p>n이 소수가 아니라고 가정하면, n은 1로 나눌 수 있을 뿐만 아니라 n이지만 i와 j로 나눌 수도 있습니다. 즉, n/i = j...0입니다. 예를 들어 15는 소수가 아니며, 15/3 = 5입니다. 예를 들어 35는 소수가 아닙니다. , 35 / 5 = 7. 이때 i와 j는 (1, Math.sqrt(n) ] 및 [Math.sqrt(n), n)에 있어야 합니다. 예를 들어 Math.sqrt(15) ≒ 3.8 , 3은 (1, 3.8]에 있고 5는 [3.8, 15)에 있습니다. 예를 들어 Math.sqrt(4) = 2이면 2는 (1,2]에 있고 [2,4)에도 있습니다. </p><pre class="brush:php;toolbar:false">function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  for (let i = 2; i <p>이때 알고리즘 복잡도는 O(sqrt(n))</p><h3 id="%E7%B4%A0%E6%95%B0%E4%B8%8D%E8%83%BD%E6%98%AF%E9%99%A4%E4%BA%862%E5%A4%96%E7%9A%84%E5%81%B6%E6%95%B0"><strong>3입니다. 소수는 2가 아닌 다른 짝수가 될 수 없습니다</strong></h3><p>2를 제외한 모든 짝수는 소수가 아닙니다</p><p><img src="https://img.php.cn/upload/image/644/149/762/1663645614907138.png" title="1663645614907138.png" alt="자바스크립트에서 소수를 찾는 방법"> </p><pre class="brush:php;toolbar:false">function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  if (n % 2 === 0) {
    return false;
  }
 
  for (let i = 3; i <p>n for 루프에서는 위 그림의 하늘색 부분만 해당됩니다. </p><p>그래서 위의 알고리즘은 루프를 절반으로 줄이고 시간복잡도는 O(sqrt(n)/2)입니다. </p><p>이 알고리즘의 코드는 n% 2 ===의 판단 조건을 추가할 수 없다는 점에 유의해야 합니다. 0 to the loop , 다음 코드에는 취약점이 있습니다</p><pre class="brush:php;toolbar:false">function isPrime(n) {
  n = parseInt(n);
 
  if (n  1;
  }
 
  for (let i = 3; i <p> 이때 4, 6, 8은 모두 소수로 판단됩니다. </p><p>이 취약점이 발생하는 이유는 for 루프의 루프 조건 i </p><p>이 알고리즘은 루프 조건 i = i^2 = 9인 경우에만 n의 n 값을 보장할 수 있습니다. </p><h3 id="%E5%A4%A7%E4%BA%8E%E7%AD%89%E4%BA%8E5%E7%9A%84%E7%B4%A0%E6%95%B0%E4%B8%80%E5%AE%9A%E5%92%8C6%E7%9A%84%E5%80%8D%E6%95%B0%E7%9B%B8%E9%82%BB"><strong>4. 5보다 크거나 같은 소수는 6의 배수에 인접해야 합니다</strong></h3><p>5보다 크거나 같은 소수는 6의 배수에 인접해야 합니다</p><p>(이 문장은 다음과 동일하지 않습니다. <span style="text-decoration:line-through;">은 6의 배수에 인접합니다. 인접한 숫자는 5보다 큰 소수여야 합니다</span>, 이 결론은 사실이 아닙니다.)</p><p><img src="https://img.php.cn/upload/image/346/360/896/166364562667908%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EC%97%90%EC%84%9C%20%EC%86%8C%EC%88%98%EB%A5%BC%20%EC%B0%BE%EB%8A%94%20%EB%B0%A9%EB%B2%95" title="166364562667908자바스크립트에서 소수를 찾는 방법" alt="자바스크립트에서 소수를 찾는 방법"></p><p>위 그림과 같이 5보다 크거나 같은 숫자는 다음과 같이 나뉩니다. -1, 6y, 6y+1, 6y+2, 6y +3, 6y+4 (y>=1)</p><p>그 중 6y, 6y+2, 6y+3, 6y+4는 소수가 될 수 없습니다. . 6y-1과 6y+1<strong><span   style="max-width:90%">만이 소수가 될 수 있습니다. </span></strong>또한 6y-1(y>=1)과 6y + 5(y>=0)는 동일합니다. </p><p>그래서 n이 6y-1(또는 6y+5) 및 6y+1이 아닌 숫자를 직접 제외할 수 있습니다. 제거 방법은 </p><pre class="brush:js;toolbar:false">  if (n % 6 !== 1 && n % 6 !== 5) {
    return false;
  }

다음으로 6y-1(또는 6y+5)을 제거해야 합니다. ) 및 6y +1의 소수가 아닌 숫자,

  for (let i = 5; i <= Math.sqrt(n); i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }

여기서 혼동되는 두 가지 사항이 있을 수 있습니다.

for 루프에서 i의 증분은 왜

6
• 결정 조건이 다음과 같은가요? for 루프의 소수 n % i = == 0 || n %
(i+2)
• === 0

위 다이어그램을 보면 6y-1이 산술이라는 것을 알 수 있습니다. 밑이 5이고 차이가 6인 수열입니다. 이는 5 + 6x입니다.

• 对于 5 + 6x 而言，如果x为5的倍数（5 * z），则5 + 6x = 5 + 6 * 5 * z = 5 *（1+6z）,则此时5 + 6x可以被5整除。
• 5 + 6x 还可以转化为 5 + 6 + 6 * (x-1) = 11 + 6(x-1)，则只要x-1为11的倍数，则5 + 6x可以被11整除，
• 5 + 6x 还可以转化为 5 + 12 + 6 * (x-2) = 17 + 6(x-2)，则只要x-2为17的倍数，则5 + 6x可以被17整除
• ......

6y+1，是基数为7，差值为6的等差数列，即 7 + 6x :

• 对于 7 + 6x 而言，如果x为7的倍数（7 * z），则7 + 6x = 7 + 6 * 7 * z = 7 *（1+6z）,则此时7 + 6x可以被7整除。
• 7 + 6x 还可以转化为 7 + 6 + 6 * (x-1) = 13 + 6(x-1)，则只要x-1为13的倍数，则7 + 6x可以被13整除，
• 7 + 6x 还可以转化为 7 + 12 + 6 * (x-2) = 19 + 6(x-2)，则只要x-2为19的倍数，则7 + 6x可以被19整除，
• ......

所以6y-1和6y+1可能整除的数自增量为6，这是for循环i自增为啥是 6的原因

且6y-1和6y+1的整除数基数为5和7，相差为2，这是for循环中素数判定的条件为啥是 n % i === 0 || n % (i+2) === 0的原因

function isPrime(n) {
  n = parseInt(n);
 
  if (n <= 3) {
    return n > 1;
  }
 
  if (n % 6 !== 1 && n % 6 !== 5) {
    return false;
  }
 
  for (let i = 5; i <= Math.sqrt(n); i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }
 
  return true;
}

此时时间复杂度为 O（sqrt(n) / 3） 

【相关推荐：javascript视频教程、编程基础视频】

위 내용은 자바스크립트에서 소수를 찾는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!