[수학] 에라토스테네스의 체를 이용한 소수 구하기

📋 [ JS 알고리즘 ] 시리즈 몰아보기 (2)

✏️ 에라토스테네스의 체를 이용하여 소수 판별하기

깃허브에서 보기

1 ~ number까지 소수를 판별할 때 가장 작은 소수인 2부터 소수의 배수를 소거해 나가면 소수를 판별할 수 있다.

number = 17일 때 진행 과정은 다음과 같다.

index값이 0과 1인 원소를 제외한 모든 원소를 true로 초기화한다. 이렇게 하면 가장 작은 소수인 2부터 17까지 true의 값을 가지게 된다.
소수인 2가 true이기 때문에 2의 배수를 모두 false로 초기화한다. => [4, 6, 8, 10, 12, 14, 16] = false
그 다음 수인 3이 true이기 때문에(=소수) 3의 배수를 모두 false로 초기화한다. => [6, 9, 12, 15] = false
그 다음 수인 4가 false이기 때문에(!=소수) 다음으로 넘어간다.
그 다음 수인 5는 true이지만 5*1, 5*2, 5*3까지 모두 판별이 완료된 상황에서 5*4가 number를 초과하기 때문에 로직을 중단한다.

1 ~ 17까지의 약수 = [2, 3, 5, 7, 11, 13, 17]

🖥️ 소스코드

          
            
          
            1
            const decimal = (number) => {
          
        

          
            2
                // 크기가 number+1인 array를 선언함과 동시에 모든 원소를 true로 채우되 0, 1은 false로 변경
          
        

          
            3
                let result = Array(number + 1).fill(true).fill(false, 0, 2);
          
        

          
            4
            
          
        

          
            5
                // 가장 작은 소수인 2부터 i^2가 number보다 크지 않을때 까지 반복
          
        

          
            6
                for (let i=2; i*i<=number; i++) {
          
        

          
            7
                    if (result[i]) {
          
        

          
            8
                        for (let j=i*i; j<=number; j+=i) {
          
        

          
            9
                            result[j] = false;
          
        

          
            10
                            /* result[i]가 true(=소수)일 경우 i ~ number까지
          
        

          
            11
                            i의 배수를 모두 false로 전환, 해당 로직을 반복한다. */
          
        

          
            12
                        }
          
        

          
            13
                    }
          
        

          
            14
                }
          
        

          
            15
            
          
        

          
            16
                // 0 제거
          
        

          
            17
                result.splice(0, 1);
          
        

          
            18
                return result;
          
        

          
            19
            }

📚 더 많은 자료(in github)
https://github.com/banma1234/algorithm_market

# 알고리즘

# JS

# javascript

# 소수

# 에라토스테네스의체

# math

💡 로그인 하지 않아도 댓글을 등록할 수 있습니다!

👨‍💻 관련 포스트

[문제해결] frequency Counter 패턴

frequency counter 패턴은 hash를 활용하는 패턴으로 빈도수를 측정하고 비교하는데 사용된다. javascript에서는 객체 혹은 Map 자료형을 이용해 구현할 수 있다. 단순 배열을 이용하는것 보다 시간복잡도를 눈에띄게 줄일 수 있다.

2023-05-11

1	const decimal = (number) => {
2	// 크기가 number+1인 array를 선언함과 동시에 모든 원소를 true로 채우되 0, 1은 false로 변경
3	let result = Array(number + 1).fill(true).fill(false, 0, 2);
4
5	// 가장 작은 소수인 2부터 i^2가 number보다 크지 않을때 까지 반복
6	for (let i=2; i*i<=number; i++) {
7	if (result[i]) {
8	for (let j=i*i; j<=number; j+=i) {
9	result[j] = false;
10	/* result[i]가 true(=소수)일 경우 i ~ number까지
11	i의 배수를 모두 false로 전환, 해당 로직을 반복한다. */
12	}
13	}
14	}
15
16	// 0 제거
17	result.splice(0, 1);
18	return result;
19	}