不依赖任何第三方库的数1方式，时间复杂度为O(n) ，用与运算方法得出结果！

以6为例 6的转二进制为110 将6-1=5，转二进制为101 110与101作与运算 (6 & (6 -1))

110 101 得到 100

结果不为0，再次和自减1作与运算 (4 & (4-1))

100 011 得到 0 上述操作执行了2次，故在6的二进制数中共2个1。

参考视频：https://www.bilibili.com/video/BV1UK411D724

#include<iostream>
#define ll long long
using namespace std;

int GetOneCount(ll x){
	int count = 0;
	if(x == 0){
		return 0;
	}
	while(x != 0){
		count++;
		x = x & (x - 1);
	}
	return count;
}

bool isPrime(int n){
	if(n == 1 || n == 0)
	{
		return false;
	}
	int flag = 0;
	for(int j = 2 ; j < n; j++)
	{
		if(n % j == 0)
		{
			flag = 1;
			break;
		}
	}
	if(flag == 0)
	{
		return true;
	}
	return false;
}

int main()
{
	ll l,r,count = 0;
	cin >> l >> r;
	for(ll i = l; i <= r;i++){
		if(isPrime(GetOneCount(i))){
			count++;
		}
	}
	cout << count;
	return 0;
}

#include<stdio.h>
#include<math.h>
//使用移位运算符和与运算判断一个数的二进制中有多少个1 
int main(){
	int l,r;
	int count = 0;//记录素数的个数 
	int flag = 1;//标记是否为素数
	int number = 0;//记录1的个数
	int sq;
	int temp; 
	scanf("%d %d",&l,&r);
	for(int i=l; i<=r; i++){
		temp = i;
		flag = 1;
		number = 0; 
		while(temp){//6 110
			if(temp & 1 == 1){
				number++;//1的个数加1 
			}
			temp = temp>>1; 
		}//判断结束退出循环
		if(number == 1){
			flag = 0;
		}
		sq = (int)sqrt((double)number);//取i的平方根
		for(int k=2; k<=sq; k++){
			if(number%k == 0){//不是素数 
				flag = 0;
				break;//终止循环 
			}
		}
		if(flag){
			count++;//是素数则++; 
		} 
	}
	printf("%d",count);	
} 

拯救公主？3ms！吊打出题人（

众所周知有一个函数

__builtin_popcount(i) 可以快速求出数再二进制下的1的个数，我们直接开整

#include<bits/stdc++.h>
using namespace std;
inline int f(int x) {
	if(x == 0 || x == 1) return 0;
	for(int i = 2;i * i <= x; ++i) if(x % i == 0) return 0;
	return 1;
}


int main(int l,int r)
{
	scanf("%d%d",&l,&r);
	int ans = 0;
	for(int i = l;i <= r; ++i)	 ans+=f(__builtin_popcount(i));
	printf("%d\n",ans);
	return 0;
}

这样就能稳定13ms

然后我们通过拼命吸氧(开O2)就能将时间压在8ms！ 其实我们至于处理到第19为素数就行

int a[]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1};
main(int l,int r){
	scanf("%d%d",&l,&r);
	int ans = 0;
	for(int i = l;i <= r; ++i)	 ans+=a[__builtin_popcount(i)];
	printf("%d\n",ans);
	return 0;
    }

这个代码3ms！

最后附上0ms的代码:(这个代码是建立在题目数据上的，所以参考度不高)

int a[]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1};
main(int l,int r){
	scanf("%d%d",&l,&r);
	if(r==1000000){
		printf("322931");
		return 0;
	}
	int ans = 0;
	for(int i = l;i <= r; ++i)	 ans+=a[__builtin_popcount(i)];
	printf("%d\n",ans);
	return 0;
}

刚才看到个 3ms 的，哈哈。我还 2 ms 呢。

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>

using namespace std;

const int maxN = 1e6 + 5;

int prime[maxN];
bool vis13[maxN];// 素数表


void getPrime() {
	memset(vis13, true, sizeof(vis13));

	vis13[0] = vis13[1] = false;
	for (int i = 2; i <= maxN / i; ++i) {
		if (vis13[i]) {
			prime[++prime[0]] = i;
		}
		for (int j = 1; j <= prime[0] && i * prime[j] <= maxN; ++j) {
			vis13[i * prime[j]] = false;
			if (i % prime[j] == 0) {
				break;
			}
		}
	}
}

int FindOneNum(unsigned int n)
{
	int count = 0;
	while (n)
	{
		n &= n - 1;  //将n与n-1异或赋予n
		count++;
	}
	return count;
}

int main(void) {
	getPrime();
	int l, r;
	cin >> l >> r;

	int ans = 0;

	for (int i = l; l <= r; ++l) {
		int temp = FindOneNum(l);
		if (vis13[temp]) {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

这道题 其实 解出来就行了，ms 什么的 不重要，就是 新手训练而已。

用位运算来解决

include<bits/stdc++.h>
using namespace std;//本题用位运算来计算整数中二进制数中1的个数 
#define ll long long   
ll l,r,ans,cnt,num;  

bool search(int x)//判断素数  
{  
    cnt=0;  
    if(x==1)
        return false;  
    for(int i=2;i*i<=x;i++)  
    {  
        if(x%i==0){  
        cnt++;  
        break;  
    }  
}
    if(cnt)  
        return false;  
    else  
        return true;  
} 
int main()  
{  
    std::ios::sync_with_stdio(false);  
    cin>>l>>r;  
    for(int i=l;i<=r;i++)  
    {  
        num=0;//重置  
        ll y=i;  
        while(y!=0)  
        {  
            y=y&(y-1);//用按位与运算消去二进制y的最后一位1   
            num++;   
        }  
            if(search(num))  
                ans++;  
    }  
    cout<<ans;  
    return 0;   
}
按位与运算：&
    如果两个相应的二进制位都为1，则该位的结果值为1，否则为0

详情请见<https://blog.csdn.net/deaidai/article/details/78167367?utm_source=app&app_version=4.21.0&code=app_1562916241&uLinkId=usr1mkqgl919blen>

#这个题可以直接用讲的位运算函数（__builtin_popcount）来解题# ##仅供参考##

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll isprime(ll x)
{
	ll ret=1;
	if(x==2) ret=1;
	if(x==1||x==0) ret=0;
	for(int i=2;i<=sqrt(x);i++)
	{
		if(x%i==0)
		{
			ret=0;
		}
	}
	return ret;
}
int main()
{
	ll m,n,k,count=0;
	cin>>m>>n;
	for(int i=m;i<=n;i++)
	{
		int k=__builtin_popcount(i);
		if(isprime(k))
		{
			count++;
		}
	} 
	cout<<count<<endl;
	return 0;
}