자바 스크립트에서 에라 토 스테 네스 (Eratosthenes)의 세그먼트 시브 구현

Question

최근 큰 숫자에 대한 에라 토 스테 네스의 세그먼트 시브 (Segmented Sieve of Seated Sieve)에 대한 기사를 읽었습니다. 내가 잘못 가지고 위치를 알아낼 수 없습니다

function sieve(low, high) { 

    var primeArray = [], ll = Math.sqrt(low), output = []; 

    for (var i = 0; i < high; i++) { 
     primeArray[i] = true; 
    } 

    for (var i = 2; i <= ll; i++) { 
     if (primeArray[i]) { 
      for (var j = i * i; j < high; j += i) { 
       primeArray[j] = false; 
      } 
     } 
    } 

    for (var i = 2; i < ll; i++) { 
     if(primeArray[i]) 
     { 
      var segmentStart = Math.floor(low/i) * i; 

      for(var j = segmentStart; j <= high; j+=i) 
      { 
       primeArray[j] = false; 
      } 
     } 
    } 

    for(var i = low; i <= high; i++) 
    { 
     if(primeArray[i]) 
     { 
      output.push(i); 
     } 
    } 

    return output; 
}; 

: 다음

는

동일의 구현입니다. 아마도 너무 오랫동안 작업 한 것 같습니다. 예를 들어

:

sieve(4,10)[5,7] 를 반환해야하지만 당신은 충분히 높은 요인 확인되지 않은 [5,7,9]

Answer 1

을 반환합니다. 이유는 제곱근 한도가 잘못 되었기 때문입니다. 변경 :

ll = Math.sqrt(low) 

ll = Math.sqrt(high) 

첫 번째 루프

을해야 또한 루프 high 포함, 마지막에 출력 루프가 동일한 작업을 수행하기 때문이다. 같은 이유로 세 번째 외부 루프도 ll까지 루프해야합니다.

세그먼트의 시작점을 계산하는 부분은 첫 번째 반복에서 소수를 제거하지 않아야합니다. 당신이 분할 부분에 ceil 대신 floor을 사용할 수 있습니다

  if (primeArray[segmentStart]) segmentStart += i; 

참고 : low이 낮을 때 1. 그래서이 추가 같은이 일반적으로 발생합니다.

function sieve(low, high) { 
 
    var primeArray = [], ll = Math.sqrt(high), output = []; 
 

 
    for (var i = 2; i <= high; i++) { 
 
     primeArray[i] = true; 
 
    } 
 

 
    for (var i = 2; i <= ll; i++) { 
 
     if (primeArray[i]) { 
 
      for (var j = i * i; j <= high; j += i) { 
 
       primeArray[j] = false; 
 
      } 
 
     } 
 
    } 
 

 
    for (var i = 2; i <= ll; i++) { 
 
     if(primeArray[i]) { 
 
      var segmentStart = Math.ceil(low/i) * i; 
 
      // need this test to ensure we are not deleting primes 
 
      if (primeArray[segmentStart]) segmentStart += i; 
 

 
      for(var j = segmentStart; j <= high; j+=i) { 
 
       primeArray[j] = false; 
 
      } 
 
     } 
 
    } 
 

 
    for(var i = low; i <= high; i++) { 
 
     if(primeArray[i]) { 
 
      output.push(i); 
 
     } 
 
    } 
 
    return output; 
 
} 
 

 
console.log(sieve(1, 20));