[백준] 베르트랑 공준

n이 n보다 작은 수의 배수에 해당하지 않으면 n은 소수

 

에라토스테네스의 체

: 소수를 판별하는 알고리즘. 소수들을 대량으로 빠르고 정확하게 구하는 방법

과정

1. 2 ~ 120까지의 모든 숫자들을 나열합니다.
2. 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수들을 모두 지웁니다. (빨간색)
3. 남아있는 숫자에서 3은 소수이므로 오른쪽에 3을 쓰고 3의 배수들을 모두 지웁니다. (초록색)
4. 남아있는 숫자에서 5는 소수이므로 오른쪽에 5를 쓰고 5의 배수들을 모두 지웁니다. (파란색)

5. 남아있는 숫자에서 7는 소수이므로 오른쪽에 7을 쓰고 7의 배수들을 모두 지웁니다. (노란색)
6. 위의 과정을 반복합니다.

7. 11 ×11 은 121 로 범위 2 ~ 120을 넘기 때문에 반복을 멈추고 남은 수(소수)들을 출력합니다.

📍 출처 : https://coding-factory.tistory.com/600\

[Algorithm] 에라토스테네스의 체 - 소수 구하기 (범위)

 

 

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(v => +v);


// 에라토스테네스의 체로 소수 골라내기

const max = Math.max(...input) * 2; //Math.max() : 입력값으로 받은 0개 이상의 숫자 중 가장 큰 숫자 반환

let prime = [];
for (let i = 0; i <= max; i++) {
  prime.push(true);
}
// 소수가 될 수 없는 0,1은 false로 미리 지정
prime[0] = false; 
prime[1] = false;


for (let i = 2; i * i <= max; i++) {
  if (prime[i])
    for (let j = i * i; j <= max; j += i) // 제곱이 범위(2n)를 넘지 않는 범위에서
      prime[j] = false;
}

// n ~ 2n의 소수들의 수를 각 출력
input.forEach(v => {
  const start = v;
  const end = v * 2;
  if (v > 0) {
    let cnt = 0; // 소수의 수를 담을 변수
    for (let i = start + 1; i <= end; i++) { // start+1은 자릿수가 0이 아닌 1부터 시작하게끔
      if (prime[i] == true) {
        cnt++;
      }
    }
    console.log(cnt)
  }
})

 

 

📍 Ref.

https://junkim.netlify.app/posts/programmers0807

JavaScript__에라토스테네스의 체 구현 - 개발꿈나무의 개발로그

https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

[Algorithm] 에라토스테네스의 체

https://doqtqu.tistory.com/140

[백준 알고리즘] 4948번, 베르트랑 공준