首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Prime Number of Set Bits in Binary Representation

Prime Number of Set Bits in Binary Representation

作者头像
用户1147447
发布2019-05-26 00:12:18
3890
发布2019-05-26 00:12:18
举报
文章被收录于专栏:机器学习入门机器学习入门

LWC 67: 762. Prime Number of Set Bits in Binary Representation

传送门:762. Prime Number of Set Bits in Binary Representation

Problem:

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:

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

思路: 判断二进制中1的个数是否为素数,int型总共32位,所以只需要枚举出<32的素数的集合,接着非常暴力,对每个在[L, R]中的数枚举即可。

Java版本:

    public int countPrimeSetBits(int L, int R) {
        boolean[] isPrime = new boolean[32];
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        for (int prime : primes) isPrime[prime] = true;
        int ans = 0;
        for (int i = L; i <= R; ++i) {
            if (isPrime[Integer.bitCount(i)]) ans += 1;
        }
        return ans;
    }

Python版本:

    def countPrimeSetBits(self, L, R):
        """
        :type L: int
        :type R: int
        :rtype: int
        """
        prime = {2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29, 31}
        ans = 0
        for num in range(L, R + 1):
            num = bin(num)
            cnt = num.count('1')
            if cnt in prime:
                ans += 1
        return ans
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年01月14日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • LWC 67: 762. Prime Number of Set Bits in Binary Representation
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档