[프로그래머스] 소수 찾기
이번 문제는 정확성 테스트뿐만 아니라 효율성 테스트도 있어서 이 두 개의 테스트에 알맞은 코드를 짜야됩니다.
저는 정확성 테스트까지는 쉽게플었는데 효율성 테스트에서 막혀서... 결국 검색해서 풀었습니다.
프로그래머스 질문하기와 소수 찾기 검색결과
"에라토스테네스의 체"라는걸 적용을 해야 효율성 테스트에 통과한다고 하네요.
검색해도 "에라토스테네스의 체"를 구현한 코드는 거의 똑같으니까
그 부분만 이해하시면 풀 수 있을 거라 생각합니다.
아래 링크의 블로그의 해결방안을 그대로 써서 풀었습니다.👇
[알고리즘] 소수 찾기-JavaScript
Algorithm Problem with JavaScript — 3day1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가
velog.io
https://junkim.netlify.app/posts/programmers0807
JavaScript__에라토스테네스의 체 구현 - 개발꿈나무의 개발로그
소수 구하기 (에라토스테네스의 체) 자바스크립트로 소수 구하기 문제를 풀던 도중, 처음 제출했던 코드가 속도가 느려서 통과하지 못했다. 어떻게 풀어나가야 할지 찾아보다가 에라토스테네스
junkim.netlify.app
해결방안 쓰기 전에 테스트는 통과했지만 효율성 테스트를 통과 못한 제 코드를 올리겠습니다.
function solution(n) {
var answer = 0;
for(let i=2; i<=n; i++){
let isPrime = true;
for(let j=2; j<= Math.sqrt(i); j++){
if(i % j === 0) isPrime = false;
}
if(isPrime) answer++
}
return answer;
}
해결방안
function solution(n) {
let arr = [];
for(let i=1; i<=n; i++) arr.push(i);
console.log(arr);
for(let i = 1; i*i < arr.length; i++){
console.log(`i:${i}, arr[${i}] : ${arr[i]}`);
if(arr[i]){
let num = arr[i];
for(let j = num*num; j<= n; j += num){
arr[j-1]=0;
}
}
}
console.log(arr);
return arr.filter(value => value !== 0).length -1;
}
해결방안 순서
- arr배열에 1~n까지의 수를 담아준다.
- "에라토스테네스의 체"를 적용하여 arr에서 소수 빼고 다 0으로 바꾼다.
- filter을 사용하여 0을 제거해준 뒤 배열의 길이를 구한다.
1단계. arr배열에 1~n까지의 수를 담아준다.
- 소수 : 1과 자기 자신으로밖에 나누어 떨어지지 않고 자기 자신의 곱셈의 역수가 없는 수
소수는 1과 자기 자신으로밖에 나누어 떨어지지 않는다고 했습니다.
그래서 1~n 사이에 있는 소수의 개수를 반환하라 했지만 1은 소수가 아니기 때문에
arr배열에 1을 넣을 필요는 없지만
2단계에서 에라토스테네스의 체를 쓸 때 좀 헷갈려서 1을 넣어주었습니다.
나중에 -1해 주면 되니까 이후에 생각하시면 됩니다.
// 1단계. arr배열에 1~n까지의 수를 담아준다.
let arr = [];
for(let i=1; i<=n; i++) arr.push(i);- let arr = []; : 1~n까지의 수를 담을 배열
- for(let i=1; i<=n; i++) arr.push(i); n번까지 반복하고 1~n이 차례대로 arr배열에 담는다.
테스트 1 (n=10)
for(let i=1; i<=n; i++) arr.push(i); -> 1~10까지 반복
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
테스트 2 (n=5)
for(let i=1; i<=n; i++) arr.push(i); -> 1~ 5까지 반복
arr = [ 1, 2, 3, 4, 5 ]
2단계. "에라토스테네스의 체"를 적용하여 arr에서 소수 빼고 다 0으로 바꾼다.
이제 1단계에서 1~n을 담은 배열을 에라토스테네스의 체를 적용해서 소수가 무엇인지를 구해야 됩니다.
에라토스테네스의 체
- 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법입니다.
- 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부릅니다.
- 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법입니다.
에라토스테네스의 체에 대한 설명을 이미지로 나타냈습니다.
이 이미지를 설명하자면
나무위키-에라토스테네스의 체에 대해한 설명을 인용하자면
임의로 1~100까지 숫자 중 소수를 찾는다고 하자면
- 1~100까지 숫자를 쭉 쓴다.
- 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다.
- 2를 제외한 2의 배수를 제거한다.
- 3을 제외한 3의 배수를 제거한다.
- 4의 배수는 제거해야 될 차례지만 2의 배수에서 이미 지워져서 4의 배수를 지울 필요 없이
다음 숫자 5의 배수를 제거한다.
이런 식으로 2배수, 3배수, ...n배수를 지우다 보면
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남습니다.
이것이 100 이하의 소수입니다.
일종의 노가다 방식이라 상당히 무식한 방법이긴 하지만,
특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우
아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로
에라토스테네스의 체보다 빠른 방법이 없습니다.
프로그래밍에도 수학적 지식이 필요하다는 걸 일깨워주는 좋은 예시입니다.
다만 에라토스테네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적입니다.
// 2단계. "에라토스테네스의 체"를 적용하여 arr에서 소수빼고 다 0으로 바꾼다.
for(let i = 1; i*i < arr.length; i++){
if(arr[i]){
let num = arr[i];
for(let j = num*num; j<= n; j += num){
arr[j-1]=0;
}
}
}
for(let i = 1; i*i < arr.length; i++)
// 테스트 1 n=10
for(let i = 1; i*i < arr.length; i++){
console.log(`i:${i}이면, arr[${i}] = ${arr[i]}`);
}- i:1이면, arr[1] = 2
- i:2이면, arr[2] = 3
- i:3이면, arr[3] = 4
if(arr[i]){for(let j = num*num; j<= n; j += num)}
// 테스트 1 n=10
for(let i = 1; i*i < arr.length; i++){
console.log(`i:${i}이면, arr[${i}] = ${arr[i]}`);
if(arr[i]){
let num = arr[i];
for(let j = num*num; j<= n; j += num){
console.log(`num:${num}이면, j = ${j}`);
}
}
}i:1 이면, arr[1] = 2
- num:2 이면, j = 4
- num:2 이면, j = 6
- num:2 이면, j = 8
- num:2 이면, j = 10
i:2 이면, arr[2] = 3
- num:3 이면, j = 9
i:3 이면, arr[3] = 4
여기서 if(arr[i])를 안 넣으시면 테스트 2는 괜찮은데 테스트 1에서 실행시간이 너무 길어져서 답이 안 나옵니다.
arr[j-1]=0; -> num의 배수는 0으로 바꾸기
// 테스트 1 n=10
for(let i = 1; i*i < arr.length; i++){
console.log(`i:${i} 이면, arr[${i}] = ${arr[i]}`);
if(arr[i]){
let num = arr[i];
for(let j = num*num; j<= n; j += num){
console.log(`num:${num} 이면, j = ${j}`);
arr[j-1]=0;
}
}
}
console.log(arr);arr[j-1]에서 j-1를 한 이유는 arr배열의 첫번째 원소부터 실행해야 되기 때문입니다.
- arr[0] = 1
- j-1 -> 1-1 =0
i:1 이면, arr[1] = 2
- num:2 이면, j = 4, arr[j-1] : 4 -> 4를 0으로 교체
- num:2 이면, j = 6, arr[j-1] : 6 -> 6을 0으로 교체
- num:2 이면, j = 8, arr[j-1] : 8 -> 8을 0으로 교체
- num:2 이면, j = 10, arr[j-1] : 10 -> 10을 0으로 교체
i:2 이면, arr[2] = 3
- num:3 이면, j = 9, arr[j-1] : 9 -> 9를 0으로 교체
i:3 이면, arr[3] = 0 -> i:1일때 2의 배수인 4를 제거했기 때문에 0임
arr = [1, 2, 3, 0, 5, 0, 7, 0, 0, 0]
테스트 1 (n=10)
arr = [1, 2, 3, 0, 5, 0, 7, 0, 0, 0]
테스트 2 (n=5)
arr = [1, 2, 3, 0, 5]
3단계. filter을 사용하여 0을 제거해준 뒤 배열의 길이를 구한다.
// 3단계. filter을 사용하여 0을 제거해준 뒤 배열의 길이를 구한다.
return arr.filter(value => value !== 0).length -1;MDN Web Docs
filter() 메서드는 주어진 함수의 테스트를 통과하는 모든 요소를 모아 새로운 배열로 반환합니다.
구문 : arr.filter(callback(element[, index[, array]])[, thisArg])
- callback :각 요소를 시험할 함수. true를 반환하면 요소를 유지하고, false를 반환하면 버립니다. 다음 세 가지 매개변수를 받습니다.
- element : 처리할 현재 요소.
- index Optional : 처리할 현재 요소의 인덱스.
- array Optional : filter를 호출한 배열.
- thisArg Optional : callback을 실행할 때 this로 사용하는 값.
// filter() 메서드 예제
const words = ['spray', 'limit', 'elite', 'exuberant', 'destruction', 'present'];
const result = words.filter(word => word.length > 6);
console.log(result); // result = ["exuberant", "destruction", "present"]
여기서는 배열의 원소가 0이 아닌 것을 구했습니다.
테스트 1 (n=10)
arr = [1, 2, 3, 0, 5, 0, 7, 0, 0, 0]
return arr.filter(value => value !== 0) -> arr = [1, 2, 3, 5, 7]
테스트 2 (n=5)
arr = [1, 2, 3, 0, 5]
return arr.filter(value => value !== 0) -> arr = [1, 2, 3, 5]
소수의 개수를 반환하는 문제 임으로 뒤에 .length를 붙였고,
1은 소수가 아님으로 -1을 해주었습니다.
테스트 1 (n=10)
arr = [1, 2, 3, 0, 5, 0, 7, 0, 0, 0]
return arr.filter(value => value !== 0).length -1; -> 4
테스트 2 (n=5)
arr = [1, 2, 3, 0, 5]
return arr.filter(value => value !== 0).length -1; -> 3
여기까지 프로그래머스 소수 찾기 해결방안에 대해 설명해보았습니다.