알고리즘 :: 소수 개수 세기, 에라토스테네스의 체

소수 개수 세기

알고리즘 : 에라토스테네스의 체

 

소수는 1과 자기 자신뿐이다.

즉 1과 자기 자신을 제외한 약수가 있으면 소수가 아니다

 

1. 소수를 알아낸다.

2. 소수로 나눠 떨어지는 모든 수를 소수에서 배재한다.

 

예를들어 1에서 100까지 소수의 개수를 확인한다면,

2부터 100까지 true로 채운다.

*1은 소수가 아니라 2부터 시작

 

가장 작은 소수는 2이다.

2로 나눠 떨어지는 4, 6, 8, 10, 12, 14, 16, 18 .... 100을 전부 False로 바꾼다.

그 다음은 3

3도 소수다.

3으로 나눠 떨어지는 6, 9, 12, 15, 18, 21 ... 99를 false로 바꾼다.

4는 false가 들어있으니 소수가 아니다 => 생략한다.

 

이 과정을 100까지 반복한다.

여기서 True의 개수만 세어주면 소수의 개수를 알 수 있다.

 

정리

앞의 소수의 배수가 아닌 녀석은 다 소수다!

2는 소수다 그래서 4, 6, 8 이 소수가 아니지

3은 2의 배수가 아니지 그래서 소수다, 그럼 6, 9, 12 ... 등 다 소수가 아니지

4는 아까 2의 배수라서 아니고

5는 앞에서 나온 수들의 배수가 아니네 그럼 소수다!

이렇게 간단할 수가

 

// VSCode에서 JavaScript 테스트 하기위한 코드
// 메모장에 테스트 케이스 넣고 prime_number.txt로 저장했다.
let fs = require('fs');
let input = fs.readFileSync('prime_number.txt')
let n = Number(input)

// 필요 변수 선언
let all_num = []
let answer = 0

// 전체 반복하고
for(let i = 2; i <= n; i++){

	// false로 표시 안된녀석 = 소수, 이러면 실행한다
    if(all_num[i] !== false){
    
    	// 이 소수의 배수들에 소수가 아니라고 false 표시해준다.
        for(let j = i * 2; j <= n; j+=i) {
            all_num[j] = false
        }
        
        // 소수의 개수를 센다.
        answer++
    }
}