Written by java-style
on 2021-09-20

Javascript 소수 찾기 - 에라토스테네스의 체

문제 : 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다.)

제한 조건

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

입출력 예

n / result

10 4 5 3

처음 접근했을 때는,

소수의 정의로부터 출발했습니다.

그러니까 1과 자기 자신으로밖에 나누어지지 않는 수.

중첩 반복문으로 1부터 자기 자신의 수까지 증가하면서

해당 수로 나누었을 때 나머지가 0으로 떨어지는 경우가

2 이상이면 카운트하는 방식으로 소수를 찾아냈습니다.

위 방식은 n의 수가 작을 때는 문제 없이 풀 수 있었지만,

n의 크기가 커지면 커질 수록 시간이 오래 걸린다는 문제가 있습니다.

n이 50000이라는 수라면, 1부터 ~ 50,000 까지 각 숫자를

다시 1부터 해당 수까지 반복하면서 나누어서 그 결과를 구하는 것이니까요.

멘붕에 빠져서 소수를 구하는 방법을 좀 찾아보았습니다.

그랬더니, 프로그래밍 선배이신 에라토스테네스 형님이 만드신 신박한 방법이 있었습니다.

에라토스테네스 선배님은 기원전 273년에 태어나셔서

무려 2300 여년 전에 저보다 먼저 소수를 빠르게 찾는 알고리즘을 고안해 내셨습니다.

코딩하던 손이 떨릴 정도로 충격적인 천재셨습니다.

그럼 에라토스네테스의 체 라고 불리우는 소수 구하기 알고리즘을 알아보겠습니다.

참고로 아직까지도 정해진 n까지의 소수를 구하는 알고리즘 중에

가장 빠르다고 합니다. 미친

에라토스테네스의 체를 요약해보자면,

소수란 1과 자기 자신으로만 나누어지는 수 입니다.

그 말인 즉슨, 배수들은 소수가 아니라는 말입니다.

모든 배수를 제외하면 나머지가 소수다. 입니다.

발상의 전환입니다.

배수들을 제외시키다보면 상당히 많은 수를 제외하기 때문에

뒤의 연산은 매우 빨라질 수 밖에 없습니다.

하나씩 찬찬히 확인해봅시다.

일단 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 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

2는 소수인데, 그렇기 때문에 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입니다.

3도 소수이기 때문에 두고서,

3의 배수를 모두 제거합니다.

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

그 다음 수는 4인데 이미 2의 배수에서 삭제되었기 때문에 넘어갑니다.

그 다음 수는 5인데 5도 소수이기 때문에 두고서,

5의 배수를 삭제합니다.

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

그 다음 수는 7인데 7도 소수이기 때문에 두고서,

7의 배수를 삭제합니다. 49와 77, 91 밖에 안남았네요.

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까지의 모든 소수를 찾았습니다.

11의 배수는 121 이기 때문에 이미 100을 초과하기 때문에

연산을 할 필요가 없습니다.

즉, n까지의 소수를 구할때, √n 이하의 수의 배수만 지우면 된다.

이것을 프로그래밍으로 표현해보자.

먼저 표를 배열로 표현해본다고 하고,

소수가 아닌 것을 false, 소수를 true로 채운다고 생각해보자.

일단, 0과 1은 소수가 아니기 때문에 n이 주어졌을 때,

n까지 채워진 배열을 만들어보자.

function solution(n){ let arr = Array(n+1).fill(true).fill(false, 0, 2); }

여기서 왜 Array(n)이 아니라 Array(n+1)이냐면,

Array()는 길이만큼 생성하는데, 만약 n이 3이었다면,

3개의 인덱스를 가진 배열을 생성하기 때문이다.

Array[0], [1], [2].

그런데 우리는 이 인덱스를 숫자로 활용할 것이기 때문에

n+1의 길이로 생성해야 3까지 생성이 되기 때문이다.

그리고 다시 0번째와 1번째 인덱스에 false를 넣어주었다.

.fill(false, 0, 2) .

이제 숫자를 제거하는 반복문을 만들어보자.

배열의 인덱스들을 탐험하면서,

소수를 놔두고 소수의 배수들을 false로 바꾸어줘야 한다.

그리고 이 로직은 이미 false인 인덱스들을 건너뛰도록 분기화(if)해줘야한다.

그리고 이 배수는 √n 이하까지만 작업하면 된다.

for(let i=2; i*i<=n; i++){ if(arr[i]){ ... } }

0과 1은 건너뛰기 때문에 2부터 시작한다.

i의 배수들을 for문으로 표현하면 아래와 같다.

for(let i=2; i*i<=n; i++){ if(arr[i]){ for(let j=i*i; j<=n; j+=i){ arr[j] = false; } } }

여기서 j가 왜 i의 제곱근이냐면,

예를 들어서 i가 5일 때, j는 시작값이 25인데

이미 10(=5*2), 15(=5*3), 20(=5*4) 들은

2,3,4의 배수이기 때문에 false로 변환된 상태이다.

그렇기 때문에 첫 시작이 5*5 = 25인 것이다.

앞서서 배수들을 제외시켰다면,

첫 시작 수는 i*i 이다.

이렇게 배수들을 제외시키면서 연산을 하다보면

뒤로 갈 수록 연산이 빨라지는 것이다.

function solution(n) { let arr = Array(n+1).fill(true).fill(false, 0, 2); for(let i=2; i*i<=n; i++){ if(arr[i]){ for(let j=i*i; j<=n; j+=i){ arr[j] = false; } } } return arr.filter(e => e).length; }

완료된 배열에서 참된 값만 남겨서 그 길이를 반환하면 된다.

이 풀이에서 2가지 배울 수 있었다.

첫째는 수가 커질 수록 늘어나는 연산에 있어서는,

값을 제외해 나가면서 탐색할 수 있는 방법을 고민해보라는 것 하나와,

true와 false 값을 배열에 넣고,

if문에서 true 조건으로 분기화하면서,

false로 바꿔주는 구문을 사용하고 filter(e => e)를 사용하는 방법이다.

쉽지 않았지만,

2300년 전 에라토스테네스 선배의 혜안을 얻었다는 것에 기뻐하며 마친다.

Javascript 소수 찾기 - 에라토스테네스의 체

from http://themarketer.tistory.com/73 by ccl(A) rewrite - 2021-09-20 01:01:18

Top