에라토스테네스의 체(Sieve of Eratosthenes) => 소수찾기 알고리즘

DALL-E 가 만든 에라토스테네스의 체(Sieve of Eratosthenes)

기존에 소수를 찾는 알고리즘을 풀었을 때는 이중 for문을 이용한 방식을 사용했습니다.

function solution(n) {
    let result = 0;
    for(i=2;i<=n;i++){
            let count = 0;
        for(j=1;j<=Math.sqrt(i);j++){
            if(i%j === 0) count++;
        }
        if(count === 1) result++;
    }
    return result;
}

문제는 이 문제의 시간복잡도는 O(n)*O(sqrt(n)) 이중 for 문으로 인해 O(n^1.5) 으로 느린 편이라는 점입니다.

프로그래머스에서 소수찾기 라는 문제를 풀다 시간초과를 당해서

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

소수 찾기에 특화되어 있는 에라토스테네스의 체를 이용하려고 합니다.

n까지의 소수m을 찾으면 1부터 n까지의 모음에서 제거하고 추가로 m의 배수들을 한번에 제거해서 반복해서 조회 할 대상들을 한번에 제거해나가는 방식입니다.

예를 들어서 1부터 100까지의 표가 있다고 해보겠습니다.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

여기서 1은 소수가 아니므로 제거하고 그 다음 수인 2는 소수입니다. 그렇다면 표에서 2의 배수들은 소수가 아니므로 전부 제거합니다.

	2	3		5		7		9
11		13		15		17		19
21		23		25		27		29
31		33		35		37		39
41		43		45		47		49
51		53		55		57		59
61		63		65		67		69
71		73		75		77		79
81		83		85		87		89
91		93		95		97		99

한번의 실행으로 확인해야 할 대상이 절반으로 줄었습니다. 그렇다면 여기서 3,4,5 를 연속으로 생각해보면 3과 5는 소수이기 때문에 3과 5의 배수들은 동일하게 전부 제거하고 4는 2의 배수이기때문에 비교하지 않습니다.

	2	3		5		7
11		13				17		19
		23						29
31						37
41		43				47		49
		53						59
61						67
71		73				77		79
		83						89
91						97

이후로 동일 한 방식을 적용하면

	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

이렇게 총 25개의 소수만 남습니다.

이제 문제 에서 갯수를 원한다면 true인 소수의 갯수만 return 해주면 되고 소수 하나하나를 원한다면 해당 true인 요소의 idx를 return해주면 됩니다. 이중 for문 사용시보다 실질적인 계산 횟수가 확 줄었습니다.  이 풀이의 시간복잡도는 O(n log log n)이기 때문에 입력이 커지면 커질 수록 그 차이가 극대화 된다는 걸 알 수 있습니다. 단순하게 생각해봐도 입력이 10만이라고 하면 1부터 100까지에서 나온 소수들의 배수들을 전부 제거하고 시작하기 때문에 기존 방식이 10만개를 전부 비교 할 동안 이 방식은 그의 절반도 안되는 수들만 비교하면 된다는 점을 알 수 있습니다.

이를 코드로 나타내면

function solution(n) {
    let arrFrime = Array(n+1).fill(true);
    arrFrime[0] = false;
    arrFrime[1] = false;
    
    for(let i=2; i<=Math.sqrt(n); i++) {
        if(arrFrime[i]) { // i가 소수인 경우
            for(let j=i*i; j<=n; j+=i) { // i의 배수들을 모두 소수에서 제외
                arrFrime[j] = false;
            }
        }
    }
    return arrFrime.reduce((acc,idx)=> idx===true ? acc+1 : acc,0)
}

풀때는 new Set으로 풀어도 좋지만 Set.has 보다 배열[i] 직접 지정이 검색 속도가 더 빠를 것이기 때문에 배열로 푸는 것을 추천합니다.