프로그래머스 레벨 1 소수 찾기 자바스크립트 풀이

📚 문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

---

📚 제한 조건

• n은 2이상 1000000이하의 자연수입니다.

---

📚 입출력 예

n	result
10	4
5	3

---

📚 입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

📚 풀리긴 하는데 의문스러운 풀이

function solution(n) {
    let answer = 0;		// 소수의 개수
    
    for(let i=2; i<=n; i++) {		// 2부터 입력받은 n 사이의 소수의 개수를 구하는 반복
        let count = 0;		// 나누어 떨어지는 수의 개수
        
        for(let j=2; j<=Math.sqrt(i); j++) {	// 소수 구하는 반복, 제곱근 사용 이유는 밑글 참조
            if(i%j === 0) {		// i/j의 나머지가 없으면, 즉 나누어 떨어지면
                count++;		// 나누어 떨어지는 수의 개수 증가
                break;		// 나누어 떨어지는 수가 있으면 소수가 아니므로 바로 for문 탈출
            }
        }
        
        if(count === 0) {		// 나누어 떨어지는 수가 없으면 소수이므로 소수의 개수 증가
            answer++;
        }
    }
    
    return answer;
}

풀고 나서 정리하는 중에 두번째 for문 안의 if문의 i % j === 0에서 이상함을 느꼈다. i = 2이고 j = 2이면 2 % 2 === 0이 맞는데 왜 count는 증가하지 않고 answer는 증가하는 것인지 의문이 들었었는데 두번째 for문의 Math.sqrt(i) 때문이었다.

j = 2일 때부터 i의 제곱근일 때까지 실행을 해야 하는데 i = 2부터 시작하면 j = 2일 때부터 2의 제곱근일 때까지 실행을 하지 못하기 때문에 두번째 for문을 실행하지 않고 바로 if(count === 0) 구문으로 넘어간다. i=2이고 j=2 일 경우를 제외하면 두 번째 for문은 잘 작동한다. 작동은 하는데 뭔가 문제의 의도랑 다르게 맞힌 것 같아서 코드를 살짝 고쳤다.

---

📚 수정한 풀이

function solution(n) {
    let answer = 0;
    
    for(let i=3; i<=n; i++) {	//2는 어차피 소수니까 3부터 시작
        let count = 0;
        
        for(let j=2; j<=Math.sqrt(i); j++) {
            if(i%j === 0) {
                count++;
                break;
            }
        }
        
        if(count === 0) {
            answer++;
        }
    }
    
    return answer+1;		//위에서 2 생략했으니까 소수의 개수에 1 더하기
}

아마 이 문제를 틀린 사람은 대부분 효율성 테스트에서 틀렸을 것이다. 나도 소수 구할때 효율적으로 구하는 방법을 몰라서 틀렸다. 소수를 효율적으로 구하려면 (구할 숫자) / 1부터 (구할 숫자) / (구할 숫자) 까지 구하면 안 되고 (구할 숫자) / 1부터 (구할 숫자) / (구할 숫자의 제곱근)까지 구하면 된다고 한다. 예를 들어 999가 소수인지 판별할 때 999 / 1부터 999 / 999까지 계산하는 것이 아닌 999 / 999의 제곱근(루트 999)까지 계산을 해야 효율적이라고 한다. 자세한 사항은 아래 영상에 있다.

https://www.youtube.com/watch?v=LD-Px5YCd8Y&t=63s 

---

📚 출처

https://school.programmers.co.kr/learn/courses/30/lessons/12921?language=javascript# 

프로그래머스