n이하의 배열을 만들고 그 배열에서 에라토스테네스의 체를 이용한다.
let num = 120;
let arr = new Array(num-1); //2부터 num까지이므로 num-1개만 생성
for(let i=0;i<num-1;i++)
arr[i] = i+2; // num-1번을 반복하며 2부터 num까지 생성
console.log(arr)
let count;
for(let i=2;i<=Math.sqrt(num);i++)
{
count = i+i; // 기존값에 2배인애들부터 체크
while(count<=num){
if(arr.indexOf(count) !== -1) // -1이 아니라면(값이 있다면)
arr.splice(arr.indexOf(count),1); //해당 값은 배수이므로 제거
count+=i; // 기존값에서 i만큼 증가해서 체크
}
}
console.log(arr)
console.log(arr.length)
해당 값보다 작은 값들에서 이미 곱셈을 처리했기 때문이다.
100을 기준으로
그렇다면 왜 10까지만 반복하는 걸까 ?
2를 가지고 위의 작업을 수행하면 2*2, 2*3, 2*4, 2*5... 2*50
까지 지워집니다.
다음으로 3을 가지고 작업한다고 했을 때 3*2, 3*3, 3*4, 3*5 .. 3*33
까지 지워집니다.
다음으로 5로 수행했을 때 5*2, 5*3, 5*4, 5*5, 5*6... 5*20
까지 지워집니다.
3의 배수를 지운다고 했을 때 3*2
는 이미 2의 배수이기 때문에 지워지고
5의 배수를 지운다고 했을 때 5*2, 5*3, 5*4
는 이미 2 또는 3의 배수여서 지워졌기 때문에 비교의 의미가 없습니다.
즉 11로 위의 작업을 수행한다고 가정한다면
11*10
이하의 자연수에서 소수가 아닌 수들은 이미 다 지워졌기 떄문에 위의 작업은 10까지만 수행하는 것입니다.
ex) num = 100
배열 및 25개의 갯수도 알 수 있다.
ex) num = 120
배열 및 30개의 갯수도 알수있다.