[JavaSrcipt] Baekjoon - 1929 : 소수찾기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제입력	예제출력
3 16	3 5 7 11 13

 

❌ 풀이

let [m,n]=require('fs').readFileSync('/dev/stdin').toString().split(' ').map(x=>Number(x));

while(m<=n){
    if(m==2||m==3||m==5){
        console.log(m);
    }
    if(m!==1&&m%2!==0&&m%3!==0&&m%5!==0){
        console.log(m);
    }
    m++;
    
}

너무 간단히생각했나보다

 

✅ 에라토스테네스의 체

2부터 시작해 자연수를 차례로 쓴 다음,

2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

입력값이 1이상 100000이하이므로 1이 들어올경우를 생각해

1이 아니면서 2,3,5로 나눈 나머지가 0이아니라면 출력하도록했는데

출력초과만 자꾸 나왔다.

 

결국틀렸다는것인데

 

❌ 풀이

let [m,n]=require('fs').readFileSync('/dev/stdin').toString().split(' ').map(x=>Number(x));

let answer=[];
for(let i=0;m<=n;i++){
    answer[i]=m;
    m++;
}

let aaa=[];
let era = [2,3,5];
for(let a=0;a<era.length;a++){
    for(let o=2;era[a]*o<=n;o++){
        aaa.push(era[a]*o);
    }
}
let set=new Set(aaa);
let bbb=[...set]


let result=answer.filter(x=> !bbb.includes(x));

console.log(result.join('\n'))

그래서 이렇게 

m부터 n까지의 배열을 만들고

n값까지 2,3,5의 배수들을 가진 배열을 만들어서

filter메소드로 차집합해주었는데 이번엔 시간초과다.

 

 

✅ 다른분의풀이

const input =  require('fs').readFileSync('/dev/stdin').toString().split(' ');
let M = Number(input[0]);
let N = Number(input[1]);

let primes = (m, n) => {
  let answer = [];
  let sieve = new Array(n + 1).fill(true);

  sieve[0] = false, sieve[1] = false; 
  
  for(let i=2; i<=n; i++) {
    if(sieve[i]) {
      for (let j=i+i; j<=n; j+=i) {
        sieve[j] = false;
      }
    }
  }
  for(let i=Math.max(2, m); i<=n; i++) {
    if (sieve[i]) answer.push(i);
  }
  return answer;
}

console.log(primes(M, N).join('\n'));

n+1인덱스까지 sieve배열을 만들어 모두 true로 채워준다.

그리고 0인덱스와 1인덱스는 0과 1이므로 false로 바꾸어주고

i=2부터시작해

sieve의 i인덱스가 참일경우 

j는 i+i  j가 n보다 작거나 같을때까지 j= j+i

sieve[j]=flase;

 

sieve의 2번째 인덱스가 참이면

j = 2+2 4가된다

그럼 sieve의 4번째인덱스는 false로 바꾸며

4에 다시 2를 더한다.

이렇게 j가 n값보다 작거나 같은경우 계속 반복.

 

즉 첫바퀴때는 i가 2이므로 n값보다 작거나같은 2의 배수를 false로 바꾸어주는 과정이다.

이후 i++하며 반복.

 

아래for문은 i는 2와 m값중 큰값으로하며  //즉 m이 3일경우 3이 시작지점이된다.

sieve[i]인덱스가 참일경우 

answer배열에 i를 넣어준다.

 

즉 0부터 n값까지 

true인덱스를 만들고   

2의배수 3의배수 등 어느 숫자의 배수인 시점에서 소수가 아니므로

false로 바꾸어주고

해당 배열에서 

true인 해당 인덱스값을 출력하는것.

 

 

 

-출처

https://www.acmicpc.net/problem/1929