C++로 구하는 설정 비트 개수가 소수인 숫자의 개수

문제 개요

이 문제에서는 두 정수 L과 R이 주어집니다. 목표는 L부터 R 사이에 있는 숫자들 중, 이진 표현에서 설정 비트(값이 1인 비트)의 개수가 소수인 숫자가 총 몇 개인지 구하는 것입니다.

예제로 이해하기

입력: L = 7, R = 12
출력: 6

각 숫자의 이진 표현과 설정 비트 개수를 살펴보면 다음과 같습니다.

7  → 111  : 설정 비트 = 2개 → 소수 ✓
8  → 1000 : 설정 비트 = 1개 → 소수 아님 ✗
9  → 1001 : 설정 비트 = 2개 → 소수 ✓
10 → 1010 : 설정 비트 = 2개 → 소수 ✓
11 → 1011 : 설정 비트 = 3개 → 소수 ✓
12 → 1100 : 설정 비트 = 2개 → 소수 ✓

범위 내 6개의 숫자 중 8을 제외한 나머지 숫자들의 설정 비트 개수는 모두 소수이므로, 정답은 6이 됩니다.

해결 접근 방법

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

1. L부터 R까지의 모든 숫자를 하나씩 순회합니다.
2. C++의 내장 함수 __builtin_popcount()를 사용하여 각 숫자의 설정 비트 개수를 구합니다.
3. 해당 개수가 소수인지 판별하고, 소수라면 카운트를 1 증가시킵니다.
4. 순회가 끝나면 최종 카운트를 출력합니다.

소수 판별은 6k±1 최적화 기법을 적용한 함수로 처리하면 효율적입니다. 이 방법은 2와 3으로 나누어 떨어지는 경우를 먼저 걸러낸 뒤, 5부터 √n까지 6씩 증가시키며 i와 i+2만 검사하는 방식입니다.

구현 코드

#include <iostream>
using namespace std;

// 소수 판별 함수 (6k±1 최적화)
bool isPrimeNumber(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

// 설정 비트 개수가 소수인 숫자의 개수를 계산
void printPrimeSetBits(int l, int r) {
    int tot_bit, count = 0;
    for (int i = l; i <= r; i++) {
        tot_bit = __builtin_popcount(i); // 설정 비트 개수 계산
        if (isPrimeNumber(tot_bit))
            count++;
    }
    cout << count;
}

int main() {
    int L = 7, R = 13;
    cout << "Total numbers with prime set bits between " << L << " and " << R << " are : ";
    printPrimeSetBits(L, R);
    return 0;
}

실행 결과

Total numbers with prime set bits between 7 and 13 are : 6

정리

이 알고리즘의 시간 복잡도는 범위의 크기를 N이라 할 때 O(N × √M)입니다(M은 확인하는 비트 개수의 최댓값). __builtin_popcount()는 대부분의 컴파일러에서 단일 CPU 명령으로 처리되므로 매우 빠르며, 소수 판별 부분만 최적화하면 넓은 범위에서도 효율적으로 동작합니다.