prime.md

Prime

문제) 1 ~ 1000사이에서 몇 개의 소수가 존재하는지 그 개수를 구하시오.

WIL(What I Learned this problem)

이 문제를 통해서 알게 된 사실들에 대해 간단하게 정리한다.

소수를 구하는 방식에 대해서

소수를 구하는 방식은 3가지가 있다.

방법1) 완전탐색

시간복잡도 O( n² ) 으로 이중for문을 통해서 해결한다.

for (let i = 1; i <= 1000; i++) {
	//1 ~ 1000까지의 숫자 반복
	for (let j = 1; j <= i; j++) {
		//각각의 숫자가 소수인지 확인
		//...
	}
}

방법2) 완전탐색 + 범위 줄이기

O( n² )으로 이중for문을 통해서 해결한다. 하지만 여기서는 반복문의 범위를 줄인다. 어떻게??

10이 소수인지 아닌지 판별해보자. 다시 한 번, 소수란 1과 자기자신으로만 나눠지는 수를 말한다.

▶ 1 2 3 4 5 6 7 8 9 10

1,2,5,10은 10의 약수이다. 10이 소수인지 아닌지를 판별하는 것은 딱 2까지만 반복을 해보면 된다. 왜냐하면 모든 약수는 대칭적으로 존재하기때문이다.

주어진 수의 처음부터 끝까지 반복해서 나눠보는 것이 아니라 주어진 수의 최대 반까지만 반복하면 된다. 여기서 사용하는 방법이 Math.sqrt()를 이용한다.

Math.sqrt()는 숫자의 제곱근을 반환한다.

for (let i = 1; i <= 1000; i++) {
	//1 ~ 1000까지의 숫자 반복
	for (let j = 1; j <= Math.floor(Math.sqrt(i)); j++) {
		//각각의 숫자가 소수인지 확인
		//...
	}
}

방법3) 에라토스테네스의 체

1~1000 사이의 소수를 구한다고 하면, 각 수의 배수를 지워가면서 최종적으로 남는 수가 소수이다.

참고

• 구현

  위에서 풀던 방법과는 약간 다르게 먼저 지워야 할 무엇인가가 필요하다. 그 말은 1~1000 까지의 숫자가 들어있는 배열이 만들어야 한다. 이 배열을 순회하면서 각 숫자의 배수를 없애야 한다.

  for (let i = 2; i < array.length; i++) {
  	for (let j = i + i; j < array.length; j += i) {
  		//배수마다 반복
  		//배수를 없애는 코드
  	}
  }

• 생각

  코드상으로 바라보면 배열을 만들어서 이중for문을 돌아야하는 것은 비슷한 상황으로 보인다. 지금까지 솔루션을 보면 공통적으로 이중for문을 사용하면서 해결하지만, 차이점은 어떻게 반복할 것인가에 맞춰져있는 것 같다.

  위 코드에서 배수를 없애는 조건을 생각해보자. 배수를 없애고 그 공간을 0으로 채운다(나는 그렇게 풀었다...) 그렇게되면 추후에 앞의 숫자와 공배수인 수는 자신이 체크할 수들이 이미 0으로 채워져있어서 반복검사를 할 필요가 없어진다. 처음에만 체크할 부분이 많고 점차적으로 반복이 진행될수록 검사할 양이 줄어들게 되는 것이다.

  반복함에 따라 체크해야 할 대상을 줄이는 방법이 이 솔루션의 포인트가 아닐까

      sol1-timer: 49.194ms
      sol2-timer: 5.060ms
      sol3-timer: 2.442ms
  

  1~1000까지의 소수를 구할 때, 실제적으로 각 솔루션이 걸리는 시간을 나타낸 것이다. 위에서도 알 수 있듯이 1000이라는 작은 숫자임에도 시간이 현저하게 차이나는 것을 볼 수 있다.

  솔루션3의 경우, 찾아본 결과 시간 복잡도가 O(n)에 근접한다고 한다. 로그가 나오고 수학적으로 접근하는 부분들이 있었다. (사실 좀 보다가...패스🤯😭)

  참고