Trong bài toán này, chúng ta được cung cấp hai số nguyên L và R. Nhiệm vụ của chúng ta là in ra tổng các số có đặt bit đếm thành một số nguyên tố nằm trong khoảng từ L đến R.
Hãy lấy một ví dụ để hiểu vấn đề
Input: L = 7, R = 12 Output: 6 Explanation: 7 -> 111 , set bits = 2, prime number. 8 -> 1000 , set bits = 1, not prime number. 9 -> 1001 , set bits = 2, prime number 10 -> 1010 , set bits = 2, prime number 11 -> 1011, set bits = 3, prime number 12 -> 1100, set bits = 2, prime number
Để giải quyết vấn đề này, chúng tôi sẽ xem xét từng phần tử trong phạm vi. Và kiểm tra tổng số bit đã đặt trong số, đối với điều này, chúng tôi sẽ sử dụng một hàm được xác định trước trong CPP _builtin_popcount (). Sau đó, chúng tôi sẽ kiểm tra các bit đã đặt của số là số nguyên tố. Nếu có, hãy tăng số lượng nếu không.
Chương trình cho thấy việc triển khai giải pháp của chúng tôi
Ví dụ
#include <iostream>
using namespace std;
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;
} Đầu ra
Total numbers with prime set bits between 7 and 13 are : 6