一个整数n=p2q,其中p,q为素数,且p≠q。比如, 12=22⋅3,那么12是符合条件的数; 18=2⋅32,所以18也是符合条件的数; 30=2⋅3⋅5,所以30是不符合条件的数。 求区间[a,b]之间有多少个符合条件的数。用c语言写一个实现此问题的代码
时间: 2023-03-13 17:05:40 浏览: 63
答案:要求[a,b]之间符合条件的数的话,可以使用素数筛法先找出[a,b]之间的素数,然后再按照条件组合出要求的结果。C语言实现此问题的代码如下:int count(int a,int b){
int res=0; //用来存放素数的个数
int *isPrime=malloc(sizeof(int)*(b+1)); //用来标记[2,b]之间的素数
memset(isPrime,1,sizeof(int)*(b+1)); //将[2,b]之间的数设为1 for(int i=2;i<=b;i++){
if(isPrime[i]){
if(i<a) //如果i小于a,说明i不满足条件,跳过
continue;
for(int j=i*i;j<=b;j+=i){
isPrime[j]=0; //把i的倍数标记为0
}
int p=i; //p为i的一个素数
for(int q=2;q<i;q++){ //q从2开始,依次往上加
if(isPrime[q] && p*q>=a && p*q<=b){ //满足条件
res++; //计数加1
}
}
}
}
free(isPrime); //释放内存
return res;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)