[LeetCode] 762. Prime Number of Set Bits in Binary Representation

😎풀이

1. countPrime: left와 right를 포함한 범위 내 소수의 수
2. left와 right를 포함한 범위 탐색
   2-1. 각 수의 1의 비트 수 탐색
   2-2. 2-1의 수가 소수인지 판별
   2-3. 소수라면 countPrime 증가
3. countPrime 반환

function countPrimeSetBits(left: number, right: number): number {
    let countPrime = 0
    for(let i = left; i <= right; i++) {
        let curLeft = i
        let countOne = 0
        while(curLeft) {
            if(curLeft & 1) countOne++
            curLeft >>= 1
        }
        if(isPrime(countOne)) countPrime++
    }
    return countPrime
};

function isPrime(n: number) {
    if(n < 2) return false
    if(n <= 3) return true
    if(n % 2 === 0 || n % 3 === 0) return false
    for(let i = 5; i * i <= n; i++) {
        if(n % i === 0 || n % (i + 2) === 0) return false
    }
    return true
}