코딩테스트 문제풀이 소수 찾기

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/12921

저작권 관련

비상업적, 비영리적 용도로 사용합니다.

광고가 노출되지 않는 블로그나 YouTube 채널, GitHub 등에 문제 풀이 게시

 

코딩테스트 연습에 공개된 문제는 (주)그렙이 저작권을 가지고 있습니다. (지문 하단에 별도 저작권 표시 문제 제외)
코딩테스트 연습 문제의 지문, 테스트케이스, 풀이 등과 같은 정보는 비상업적, 비영리적 용도로 게시할 수 있습니다.

※ 2020 KAKAO BLIND RECRUITMENT, Summer/Winter Coding 등의 문제는 기업 코딩 테스트에 나온 문제이나, 

코딩테스트 연습에 공개된 문제이기 때문에 마찬가지로 비상업적, 비영리적 용도로 게시할 수 있습니다.

(2021. 01. 08 업데이트)

 

 

문제 설명

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를 반환

---

 

위 문제를 풀때 고려해야하는 사항.

1. 1은 소수가 아니니 제외한다.

2. 시간초과가 있어 효율적으로 풀어야 한다.

 

 

접근방법.

1. 소수를 찾는 알고리즘인 에라토스테네스의 체를 이용한다.

에라토스테네스의 체란?
소수를 찾는 데 효과적인 알고리즘,
2부터 자기자신을 제외한 배수를 제외해 나간다.
ex)
2를 남기고 4, 6, 8, 10... 2n제거
3를 남기고 6, 9, 12, 15... 3n제거
4를 남기고 8, 12, 16, 20... 4n제거
5를 남기고 10, 15, 20, 25... 5n제거
....
(단. 이미 이전에 지워진 수라면 지우지 않고 넘어간다.)

 

 

function solution(n) {

    //1부터 n까지 연속된 숫자가 들어간 배열을 만든다.
    const arr = Array.from(Array(n), (_, i) => i + 1);
    
    //1은 소수가 아니니 미리 지워둔다.
    arr[0] = 0;
    
    //answer는 지울 숫자의 갯수, 위에서 1을 먼저 지웠으니 초기값은 1로 한다.
    let answer = 1;
    
    //2부터 1씩 증가하는 반복문을 돌린다.
    for (let i = 2; i <= n; i++) {
    
    	//이미 지워진 숫자라면 해당 배수는 이미 다 지워졌으니 2중 반복문을 돌지 않아도 된다.
        if(arr[i - 1] === 0) continue;
        
        //자기자신을 제외한 배수를 다 지운다.
        for (let j = i * 2; j <= n; j += i) {
        
                //arr index는 0부터 시작하니 j - 1
                if (arr[j - 1]) {    //숫자가 있으면 
                    answer ++;       //answer를 1증가시키고
                    arr[j - 1] = 0;  //arr에서 지운다.
                }
        }
        
    }
    
    //n에서 지운 숫자의 갯수을 빼서 리턴한다.
    return n - answer; 
}