✅문제
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
❕ 제한사항
- n은 2이상 1000000이하의 자연수입니다.
🎹📢입출력 예제
✍풀어보기
function solution(n) {
let answer = 0;
const arr = new Array(n+1).fill(true);
for(let i = 2; i <= n; ++i){
// 이미 소수가 아닌 인덱스는 건너뛴다.
if(arr[i] === false){
continue;
}
// 배수는 소수가 아니라 0으로 설정
for(let k = i * 2; k <= n; k += i){
arr[k] = false;
}
}
// 소수의 갯수를 구한다.
for(let i = 2; i <= n; ++i){
if(arr[i] === true){
answer++;
}
}
return answer;
}소수 문제를 봤을 때 배열 없이 더 빠른 방법이 없을까 고민하다가 못 찾고, 소수를 공부할 때 체를 걸러주듯 숫자의 배수들을 지워주는 방법이 떠올랐는데 뭔지 이름이 생각 안 나서 찾아보고 다시 문제를 풀었다. 수학자 에라토스테네스가 소수를 찾는 방법을 발견했는데 그것이 에라토스테네스의 체 였다. 방법은 이러하다.
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다.
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
- 자기 자신을 제외한 3의 배수를 모두 지운다.
...
위의 방법대로 배수를 모두 지우면 남아있는 수는 소수가 된다. 엄청나게 효율적인 방법이다.
테스트 결과 적확성과 효율성 모두 잘 통과했다. 그래도 이번에는 뭔가 머리를 좀 쓴 것 같은 문제였다.
🎈다른 사람의 풀이
function solution(n) {
const s = new Set();
for(let i=1; i<=n; i+=2){
s.add(i);
}
s.delete(1);
s.add(2);
for(let j=3; j<Math.sqrt(n); j++){
if(s.has(j)){
for(let k=j*2; k<=n; k+=j){
s.delete(k);
}
}
}
return s.size;
}
// 또 다른 방법
function solution(n) {
var arr = [];
var cnt = 0;
for (var i = 0; i < n + 1; i++) {
arr.push(true);
}
for (var i = 2; i * i <= n; i++) {
if (arr[i]) {
for (var j = i * i; j <= n; j += i) {
arr[j] = false;
}
}
}
arr.splice(0, 2, false, false);
for(var i = 0; i <arr.length; i++) {
if(arr[i]) cnt++;
}
return cnt++;
}첫 번째 문제 풀이 방법은 Set을 사용해서 푸는 방법이 신선했다. 우선 Set은 중복되지 않은 유일한 값을 저장할 수 있는 배열이다. 나도 문제를 풀 때 배열의 요소 자체를 지우면 더 빠르지 않을까 생각했는데 Set을 이용해 소수가 아닌 숫자들은 지워주면 된다.
그리고 첫 번째 반복문에서 입력된 숫자의 제곱근까지 반복하면서 Set에 값이 존재하는지 확인하고 존재한다면 그 수의 배수들을 다 지워준다.
결과적으로 테스트 케이스를 보면 속도가 아주 느려 효율성이 떨어진다. 이유는 Set.has()와 Set.delete() 함수 때문인 것 같다. 아무래도 has는 Set에서 모든 요소를 순회하여 있는지 없는지 판단해야 하기 때문이고 배열의 특성상 delete는 배열의 크기가 바뀌어 재할당하거나 요소를 앞으로 땅겨 이동시켜야 하기 때문이다.
두번째 문제 풀이 방법은 그다지 좋아 보이지는 않은데 첫 번째 보다는 성능이 좋고 내가 푼 방법 보다는 느렸다. 다른 풀이와 비슷하게 제곱근 만큼의 반복을 돌면서 제곱의 수 부터 전체를 찾아 소수가 아닌 설정을 해줬다.
여기서 내가 푼 방법과 조금 다른점은 초깃값이 var j = i * i 부분이다.
내 풀이에서는 let k = i * 2인데 위의 설정이 조금 더 반복하는 횟수가 줄어서 효율적으로 보인다.
그다음 소수를 제외하고 또 배열 첫 번째 인덱스 부터 2개의 요소의 값을 지우고 false로 채워 넣었다. 그래서 0번째 인덱스부터 소수인 데이터를 카운트한다. 근데 굳이 여기서 첫 번째 인덱스로 시작할 이유는 없어 보인다.
결론적으로 내가 푼 방법에 위의 효율적인 장점들을 종합해 아래 코드를 완성 시켰다.
결론적으로 효율적인 코드
function solution(n) {
let answer = 0;
const arr = new Array(n+1).fill(true); // 초깃값 설정
const end = Math.sqrt(n)
for(let i = 2; i <= end; ++i){
// 이미 소수가 아닌 인덱스는 건너뛴다.
if(arr[i] === false){
continue;
}
// 소수가 아닌 데이터는 false로 입력한다.
for(let k = i * i; k <= n; k += i){
arr[k] = false;
}
}
// 소수의 갯수를 구한다.
for(let i = 2; i <= n; ++i){
if(arr[i] === true){
answer++;
}
}
return answer;
}참고 자료 및 사이트 (감사합니다)
