-
백준 1929번 소수 구하기알고리즘 2022. 5. 14. 16:57
출처 링크:
https://www.acmicpc.net/problem/1929
처음 나의 풀이
// 에라토스 테네스의 체 이용하기? 근데 이건 소수가 있는 지 없는 지 판별할 때 썼던 것 같은데?? // 각각의 수가 1과 자기 자신을 제외한 약수가 있는지 없는지 판별해야 함 // 1과 자기 자신 사이의 수 중에서 자기자신 나누기 특정 수를 했을 때 나머지가 0인 경우가 있다면 제외처리 // m은 1이상 n은 2이상이 되어야 소수가 적어도 1개 이상 나올 수 있음 // 입력값 const m = 3 const n = 16 let answer = [] let count = 0 if (m === 1) { answer.push(2) for (let i = 2; i <= n ; i++) { for (let j = 2; j <= Math.sqrt(i) ; j++) { if (i%j === 0) { // i가 1과 자기 자신 말고도 나누어지는 정수가 있는 경우, 소수가 아닌 경우 count++ } // count가 1이상일 경우 i는 소수가 아님 if (1 <= count) { count = 0; continue; } else { answer.push(i); count = 0; } } } } else { for (let i = m; i <= n ; i++) { for (let j = 2; j <= Math.sqrt(i) ; j++) { if (i%j === 0) { // i가 1과 자기 자신 말고도 나누어지는 정수가 있는 경우, 소수가 아닌 경우 count++ } // count가 1이상일 경우 i는 소수가 아님 if (1 <= count) { count = 0; continue; } else { answer.push(i); count = 0; } } } } console.log(answer)
나름 머리를 굴려가며 풀었지만 예제의 입력과는 다르게 나온다.
잘못된 부분을 짚기 위해 이전에 제출한 풀이를 참조해보았다.
이 풀이는 하단의 링크를 참조하여 제출한 풀이이다.
https://velog.io/@gkswn45/JavaScript-백준-1929번-소수구하기
참조한 풀이를 내식대로 다시 해석해본 것
let M = 1; let N = 5; /* 배열의 첫 시작은 1이 아닌 0이며 연산을 편히 하기 위해 배열의 길이를 1 늘려줌, 또한 첫 시작인 인덱스 1은 false처리 해주어 답에서 항상 빼주도록 함, 1은 소수에 들어가지 않기 때문 */ const isPrime = Array(N + 1).fill(true); console.log(isPrime,'isPrime') // M이 1인 경우는 제외 isPrime[1] = false; console.log(isPrime,'isPrime22222') for (let n = 2; n <= Math.ceil(Math.sqrt(N)); n++) { // 에라토스테네스의 체 원리 이용 if (isPrime[n]) { let m = 2; // m이 2부터 시작하기 때문에 n 자기 자신은 그대로 소수 목록에 들어갈 수 있다. // Q) 그렇다면 n이 4가 되는 등 소수가 아닌 수가 될 땐 어떻게 되나? // A) 이미 n이 2일때 부터 시작했기 때문에 2*2인 4는 앞의 연산에서 false로 제외되었다. // 따라서 n자체가 소수가 아닌 경우에도 문제는 없다. while (n * m <= N) { isPrime[n * m] = false; /* 애초에 n이 자기 자신과 1말고도 나눌 수 있는 수가 있다는 소리! 소수가 아님 */ m++; // n과 m 두 수를 1씩 증가 시켜서 하나 하나 확인함 } } } console.log(isPrime, "isPrime333333") const answer = []; for (let n = M; n <= N; n++) { if (isPrime[n]) { answer.push(n); } } console.log(answer, "answer") console.log(answer.join("\n")); // 자바스크립트의 특성상 자동으로 숫자 -> 문자열로 형변환이 이루어짐
위 내용의 출력 결과는 다음과 같다.
[ true, true, true, true, true, true ] isPrime // boolean 형 [ true, false, true, true, true, true ] isPrime22222 [ true, false, true, true, false, true ] isPrime333333 [ 2, 3, 5 ] answer // 숫자형 2 // 문자형 3 5
이에 따라 백준에 제출한 양식
let fs = require("fs"); let input = fs.readFileSync("/dev/stdin").toString().trim().split(" "); let M = Number(input[0]); let N = Number(input[1]); const isPrime = Array(N + 1).fill(true); isPrime[1] = false; for (let n = 2; n <= Math.ceil(Math.sqrt(N)); n++) { if (isPrime[n]) { let m = 2; while (n * m <= N) { isPrime[n * m] = false; m++; } } } const answer = []; for (let n = M; n <= N; n++) { if (isPrime[n]) { answer.push(n); } } console.log(answer.join("\n"));
이렇게 정리하긴 했지만
소수 활용 부분은 좀 더 이해와 연습이 필요한 것 같다.
추후 또 복습하여야 겠다.
'알고리즘' 카테고리의 다른 글
백준 1011번 Fly me to the Alpha Centauri (0) 2022.05.29 백준 1110번 더하기 사이클 (0) 2022.05.23 백준 10250번 ACM 호텔 (0) 2022.05.09 백준 2869번 달팽이는 올라가고 싶다. (0) 2022.05.09 백준 4948번 베르트랑 공준 (0) 2022.05.09