Math.sqrt 를 이용한 소수(Prime number)구하는 방법

(레퍼런스를 보고도 꽤 오랜 시간동안 고민하게 했던 문제를 소개하고자 합니다. 시작한지 일주일도 안된 코린이에겐 너무 힘든 문제였습니다 ㅜㅠ)

2이상의 수를 인자로 받고 2부터 그 수 까지의 소수를 구해 리턴할것

function listPrimes(num) {}

즉, num>=2 여야 하는데, 리턴값은 '2' '2-3-5' '2-3-5-7' ....의 string타입이어야 하며 이중반복문을 사용해야 한다. 정신을 가다듬고, 차근차근 처음부터 풀어보기로 한다.

2는 무조건 포함된다.

num>=2라면 리턴값에 '2'는 무조건 포함된다. 왜? 2는 num>=2를 만족하는 가장작은 소수이니까. 즉, num>=2의 num에 어떤 값을 넣어도 '2'는 무조건 포함하고 있다. 따라서 이를 위해 '2'를 할당할 변수를 선언해준다.

function listPrimes(num) {
let result= '2';
}

2를 넘는 홀수에서 소수를 찾는다.

홀수에서만 소수를 찾는다. 짝수는 무조건 약수로 2를 가지기 때문에 찾아서 소수인지 확인하는 작업은 무의미하다. 3에서 시작해 num까지의 홀수를 찾는 반복문을 사용한다. 즉, 수가 3에서 2씩 커져간다.

function listPrimes(num) {
	let result= '2';
	for (let i = 3; i <= num; i += 2){}
}

소수 여부를 Boolean으로 판단하는 변수를 만든다.

소수가 맞다면 리턴에 포함시키고 아니면 탈락시키기 위해 여부를 boolean으로 받는다. 이를 위해 변수를 만들어 할당한다.

function listPrimes(num) {
	let result= '2';
	for (let i = 3; i <= num; i += 2){
    	let isPrime = true;}
}

소수 여부를 판단하기 위해 i의 제곱근을 구하고 할당한다.

여기서부터 정말 왜지???라는 생각으로 엄청나게 많이 고민했다. 제곱근이 약수이기 때문에 그 수를 제곱근으로 나눴을 때 0이 된다면 소수라고 할 수 없다. 이를 이용하기 위해 제곱근을 구하고, 제곱근과 같거나 작은 정수 중 가장 큰 정수를 변수에 할당한다.

function listPrimes(num) {
	let result= '2';
	for (let i = 3; i <= num; i += 2){
    	let isPrime = true;
        let sqrt = Math.floor(Math.sqrt(i))}
}

제곱근과 약수를 파악하기 위한 반복문을 만들어준다.

해당 조건에 맞는다면 소수가 아닌 조건문을 만든다. 단, 이는 9아래의 소수를 위해 j <= sqrt일때만 확인할 수 있으며 j > sqrt 이면 for문에서 나간다. 만약 i를 j로 나눈 나머지가 0이라면, 소수가 아니기 때문에 isPrime에 false를 재할당한다.

function listPrimes(num) {
	let result= '2';
	for (let i = 3; i <= num; i += 2){
    	let isPrime = true;
        let sqrt = Math.floor(Math.sqrt(i))
        for (let j = 3; j <= sqrt; j+= 2) {
        	if (i % j === 0) {
        		isPrime = false;
      		}
        }
     }
}

소수일 경우에 이를 result에 더하고 result 를 재할당한다.

num이 소수일 경우 처음에 선언했던 result에 더해준 후, 재할당 시켜준다. 그리고 반복문의 조건이 끝나면 result를 리턴해준다.

function listPrimes(num) {
  let result = '2';
  for (let i = 3; i <= num; i += 2) {
    let isPrime = true;
    let sqrt = Math.floor(Math.sqrt(i))
    for (let j = 3; j <= sqrt; j+= 2) {
      if (i % j === 0) {
        isPrime = false;
      }
    }
    if (isPrime === true) {
      result = `${result}-${i}`
    }
  }
  return result;
}

너무 어려워서 토하고 싶었던 문제였다...다들 고개도 끄덕이고 대답도 잘해서 괜히 기가 죽었다. 하지만 교육매니저님께서 이제 코딩 배운지 3일 됐다고, 어려운게 당연하다고 말해서 다시 정신 차렸다. 결국 코드를 이해하고 그 내용을 블로그에 정리했다는 점에서 스스로에게 잘했다고 해주고 싶다.