[알고리즘] 소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

나의 풀이

function solution(n) {
    let array = new Array(n+1).fill(true);
    array[0] = false;
    array[1] = false;
    let sqrtN = Math.sqrt(n);
    
    for(let i = 2; i <= sqrtN; i++) {
        if(array[i]) {
            for(let j = i*i; j <= n; j += i) {
                array[j] = false;
            }
        }
    }
    
    let primeCount = array.filter(val => val).length;
    return primeCount;
}

무슨무슨 체 알고리즘을 사용해서 풀었다. 

소수 구하는 문제는 그냥 공식을 외워두고 나오면 푸는 것 같다. 

 

2부터 시작해서 모든수가 소수라고 생각하고 배수를 전부 소수가 아니라고 판단하는 방식으로 

최후에는 배수가 없는 값만 true로 남는다. 

 

이것은 소수 개수구하는 것 뿐만아니라 이 원리를 역으로 이용하면 소수인지 판단이 가능하다. 

 

특정 값의 제곱근까지를 반복해서 나눠지는 게 있다면 소수가 아니고 안나눠지면 소수이다. 

const prime = () => {
  if(num < 2) return false
  if(num % 2 ===0) return num === 2? true : false
  
  let sqrtN = Math.sqrt(n);
    
  for(let i = 3; i <= sqrtN ; i+=2){
  	  if(num % i ===0){
       	return false
      }
  }
  return true
}