Trong bài toán này, chúng ta được cho hai số nguyên L và R. Nhiệm vụ là in ra tổng số lượng các số có số bit đặt (set bits) là một số nguyên tố trong khoảng từ L đến R.
Hãy xem ví dụ sau để hiểu rõ vấn đề:
Input: L = 7, R = 12 Output: 6 Giải thích: 7 -> 111, set bits = 2, số nguyên tố. 8 -> 1000, set bits = 1, không phải số nguyên tố. 9 -> 1001, set bits = 2, số nguyên tố. 10 -> 1010, set bits = 2, số nguyên tố. 11 -> 1011, set bits = 3, số nguyên tố. 12 -> 1100, set bits = 2, số nguyên tố.
Để giải quyết, ta duyệt qua từng phần tử trong khoảng. Kiểm tra tổng số bit đặt trong số, dùng hàm có sẵn trong C++ là __builtin_popcount(). Sau đó kiểm tra xem số bit đặt đó có phải số nguyên tố hay không. Nếu có, tăng biến đếm.
Chương trình minh họa triển khai giải pháp:
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<<"Tổng số có bit đặt là số nguyên tố giữa "<<L<<" và "<<R<<" là : "; printPrimeSetBits(L, R); return 0; }Kết quả
Tổng số có bit đặt là số nguyên tố giữa 7 và 13 là : 6