[에라토스테네스의 체] 4948번 베르트랑 공준

let input =require('fs').readFileSync('./input.txt').toString().trim().split('\n').map(e=>Number(e));
// console.log(input)
// console.log(nums);
input.pop();
let nums=input;
// console.log(typeof(nums[0]));
let number = nums.map(e=>Number(e));
let max= 2*Math.max(...number);
let primes=[]
let sample=[]
for(let i=2; i<= max;i++){
  sample.push(i);
}
while(sample.length){
  let a=sample.shift()
  primes.push(a);
  sample=sample.filter(e=>(e%a)!==0);
}
// console.log(typeof(primes[0]))
// console.log(primes);
nums.forEach(ele=>{
  console.log(primes.filter(e=> e>ele&& e<=2*ele ).length)

})

중학교1학년이면 다루는 에라토스테네스의 체이다. 그닥 특별한 건 없지만 나는 메모리 초과 문제가 발생했다.. 

추후에 수정해서 더 작성해보도록 하자.

let input =require('fs').readFileSync('./input.txt').toString().trim().split('\n').map(e=>Number(e));
// console.log(input)
// console.log(nums);
input.pop();
let nums=input;
let number = nums.map(e=>Number(e));
let max=123456;
let primes=[]
let sample= new Array(max*2+1).fill(true);

sample[0]=false;
sample[1]=false;

let i=0;
for( let i=2; i< sample.length;i++){
  if( sample[i]) primes.push(i);
  for(let j= 2*i; j<= 2*max;j+=i){
    sample[j]=false;
  }
}

nums.forEach(ele=>{
  console.log(primes.filter(e=> e>ele&& e<=2*ele ).length)

})

2부터 마지막 숫자까지 순회하도록한다. 이떄 j+=i가 핵심이다. 

체 구현은 이렇게 하자... 번외로

정말 깔끔한 python 코드를 발견해서 첨부한다.

https://doqtqu.tistory.com/140

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

9020번 골드바흐의 추측역시 체 알고리즘으로 푸는 것이 가능하다.