소수 찾기 알고리즘

KHW·2021년 4월 23일
0

알고리즘

목록 보기
19/37

사용법

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)

횟수를 Math.sqrt(num)이하로 한 이유

해당 값보다 작은 값들에서 이미 곱셈을 처리했기 때문이다.

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개의 갯수도 알수있다.

출처: 개발공부블로그

profile
나의 하루를 가능한 기억하고 즐기고 후회하지말자

0개의 댓글