Python – 이진 표현에서 설정된 비트 수가 소수인 숫자 개수 구하기

문제 설명

두 정수 L과 R이 주어졌을 때, [L, R] 범위(양 끝값 포함)에 속한 숫자 중 이진 표현에서 설정된 비트(set bit)의 개수가 소수인 숫자의 개수를 구하는 것이 목표입니다.

예를 들어 입력이 L = 6, R = 10이라면 결과는 4가 됩니다. 그 이유는 다음 4개의 숫자 모두 설정된 비트의 개수가 소수이기 때문입니다.

6 → 110₂ (설정된 비트 2개)
7 → 111₂ (설정된 비트 3개)
9 → 1001₂ (설정된 비트 2개)
10 → 1010₂ (설정된 비트 2개)

참고로 8은 1000₂로 설정된 비트가 1개뿐이므로(1은 소수가 아님) 개수에서 제외됩니다.

해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

count를 0으로 초기화합니다.
j를 L부터 R까지 하나씩 반복하면서,
j의 설정된 비트 개수가 [2, 3, 5, 7, 11, 13, 17, 19] 목록에 포함되어 있는지 확인하고, 포함되어 있다면 count를 1 증가시킵니다.
반복이 끝나면 최종 count 값을 반환합니다.

소수 목록이 19까지만 필요한 이유는, 일반적인 제약 조건(R ≤ 10⁶)에서 숫자의 이진 표현 길이가 최대 약 20비트이므로 설정된 비트의 개수 역시 19 이하의 소수만 가능하기 때문입니다.

구현 코드

class Solution:
   def countPrimeSetBits(self, L, R):
      def popcount(i):
         return bin(i)[2:].count('1')
      count = 0
      for j in range(L, R+1):
         if popcount(j) in [2,3,5,7,11,13,17,19]:
            count += 1
      return count

ob = Solution()
print(ob.countPrimeSetBits(6, 10))

코드 설명

내부 함수 popcount(i)는 정수 i를 이진수 문자열로 변환한 뒤(bin(i)[2:]는 '0b' 접두사를 제거함), 문자열에서 '1'의 개수를 세어 설정된 비트의 개수를 반환합니다. 이후 각 숫자에 대해 popcount 값이 미리 정의된 소수 목록에 속하는지 검사하여 카운트를 누적하는 방식입니다.

실행 결과

입력

6, 10