PrimeNumberOfSetBitsInBinaryRepresentation [source code]

public class PrimeNumberOfSetBitsInBinaryRepresentation {
static
/******************************************************************************/
class Solution {
    public int countPrimeSetBits(int L, int R) {
        int res = 0;
        int[] memo = new int[32];
        for (int i = 0; i < memo.length; i++)
            memo[i] = -1;
        for (int i = L; i <= R; i++) if (isPrime (Integer.bitCount (i), memo)) {
            res++;
        }
        return res;
    }

    boolean isPrime (int n, int[] memo) {
        if (n == 1)
            return false;
        if (n == 2)
            return true;
        if (memo[n] >= 0)
            return memo[n] == 1;
        int limit = (int) Math.sqrt (n);
        int res = 1;
        for (int i = 2; i <= limit; i++) {
            if (n % i == 0) res = 0;
        }
        memo[n] = res;
        return res == 1;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PrimeNumberOfSetBitsInBinaryRepresentation.Solution tester = new PrimeNumberOfSetBitsInBinaryRepresentation.Solution();
        int[] inputs = {
            6, 10, 4,
            10, 15, 5,
            842, 888, 23,
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int L = inputs[3 * i], R = inputs[3 * i + 1], ans = inputs[3 * i + 2];
            System.out.println (Printer.separator ());
            int output = tester.countPrimeSetBits (L, R);
            System.out.printf ("%d and %d -> %s, expected: %d\n", 
                L, R, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

没什么特别好的办法, 乱写;

好久没有写prime test了, 居然有点手生. 最后的速度是24ms (NA);

editorial的解法, 更加的粗暴:

class Solution {  
    public int countPrimeSetBits(int L, int R) {  
        int ans = 0;  
        for (int x = L; x <= R; ++x)  
            if (isSmallPrime(Integer.bitCount(x)))  
                ans++;  
        return ans;  
    }  
    public boolean isSmallPrime(int x) {  
        return (x == 2 || x == 3 || x == 5 || x == 7 ||  
                x == 11 || x == 13 || x == 17 || x == 19);  
    }  
}

因为我们这个测试的上限其实只有这么几个, 所以直接枚举就行了;

或许你应该记住这么几个small prime?

discussion: 如果要自己数bit的话:

class Solution {  
    public int countPrimeSetBits(int l, int r) {  
        Set<Integer> primes = new HashSet<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ));  
        int cnt = 0;  
        for (int i = l; i <= r; i++) {  
            int bits = 0;  
            for (int n = i; n > 0; n >>= 1)  
                bits += n & 1;  
            cnt += primes.contains(bits) ? 1 : 0;  
        }  
        return cnt;          
    }  
}

Problem Description

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10  
Output: 4  
Explanation:  
6 -> 110 (2 set bits, 2 is prime)  
7 -> 111 (3 set bits, 3 is prime)  
9 -> 1001 (2 set bits , 2 is prime)  
10->1010 (2 set bits , 2 is prime)

Example 2:

Input: L = 10, R = 15  
Output: 5  
Explanation:  
10 -> 1010 (2 set bits, 2 is prime)  
11 -> 1011 (3 set bits, 3 is prime)  
12 -> 1100 (2 set bits, 2 is prime)  
13 -> 1101 (3 set bits, 3 is prime)  
14 -> 1110 (3 set bits, 3 is prime)  
15 -> 1111 (4 set bits, 4 is not prime)

Note:

1. L, R will be integers L <= R in the range [1, 10^6].
2. R - L will be at most 10000.

Difficulty:Easy
Total Accepted:1.8K
Total Submissions:3.5K
Contributor:lokendrajain1994
Companies
amazon
Related Topics
bit manipulation

Hint 1
Write a helper function to count the number of set bits in a number, then check whether the number of set bits is 2, 3, 5, 7, 11, 13, 17 or 19.