소수 구하기 공식

그 어떤 소수도 제곱근보다 큰 수로 나눠지지 않기 때문에 index를 제곱하여 모든 인덱스를 순회하는것보다 시간 복잡도를 개선하고 나머지 값이 0이 반환되면 소수가 아니고 반환되면 소수 → 숫자 하나만의 소수를 판별할때는 가장 효율적임

특정 범위에서 소수들을 구할때

typescript복사
const getPrimes = (num:number) => {
    const prime = [false,false,...Array(num-1).fill(true)];
    for(let i=2; i*i<=num;i+=1) {
        if(prime[i]) {
						//2 부터 시작
						//2의 배수 -> 즉 4부터 모두 false로 (배수들은 다 소수가 아니기 때문)
            for(let j=i*2; j<=num; j+=i) {
                prime[j] =false;
            }
        }
    }
//[false, false, true, true, false, true]
    return prime
}

console.log(getPrimes(5))

에라토스테네스의 체를 사용.

0과 1을 소수가 아니기 때문에 배열에서 false로 만들고 나머지는 일단 기본값으로 true를 설정

2부터 시작하여 특정 수의 배수를 모두 지운다. 즉 2부터 시작하면 하단 반복문에서 2의 배수가 모두 false로 소수가 아님을 나타냄. 똑같은 방식으로 계속 반복한다.

그럼 true인것의 인덱스 값들이 소수이며,

위의 결과값은 2,3,5가 소수로 나오고 소수의 총 갯수를 구하려면 return prime.filter((boolean)=>boolean === true).length를 하면된다.