[蓝桥杯 2023 国 B] 双子数

2024-04-07 07:12

文章标签 2023 蓝桥双子

本文主要是介绍[蓝桥杯 2023 国 B] 双子数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[蓝桥杯 2023 国 B] 双子数

B 双子数

若一个正整数 $x$ 可以被表示为 $p^2 \times q^2$ ，其中 $p$ 、 $q$ 为质数且 $\neq q$ ，则 $x$ 是
一个 “双子数”。请计算区间 $[2333, 23333333333333]$ 内有多少个 “双子数”？

输入格式

输入一个大写字母，表示第几个问题。

输出格式

根据所输入的问题编号，输出对应问题的答案。

答案：
947293

知识点1：
判断素数（欧式筛选）

//1.定义最大上限
const int n=10000010;
//2.定义判断素数数组，1：不是素数 0：是素数
bool f[n]={1,1};//0,1不素数
//3.定义动态数组：储存素数
vector<int> v;
//4.找素数
for(int i=2;i<=n;i++) //第一次循环枚举 2~n的数{if(f[i]!=1) // 如果是素数，放进数组里面v.push_back(i);for(int j=0;j<v.size()&&i*v[j]<=n;j++)//i*v[j] 不能超过上限/*j是枚举现在找到的素数，假如有一个素数是a,我们要标记的是 2*a,3*a,4*a,5*a一定不是素数而前面的系数就是我们枚举的i,素数就是遍历数组得到的v[j]i*v[j] 标记的合数 	  */{f[i*v[j]]=1;if(i%v[j]==0)break; //120=2*3*20 //有两个质因子 2，3 我们仅仅需要标记最小的那个 如果能被整除 就跳出循环  }}

埃式筛选：

//埃氏筛法
int n=1e5;
bool shai[n];
//vector<int >shai;
int cun[n];
signed main()
{int cnt = 0;//如果你用的是vector,则进行注释部分操作//shai.push_back(1), shai.push_back(1);//在0,1两个位置先添加。0，1都不是素数所以都添1。//for (int i = 2; i <= n; i++)//{//    shai.push_back(0);//}for (int i = 2; i <= n; i++){if (!shai[i])//如果没有被标记{cun[cnt++] = i;for (int j = 2; j <= n; j++){if (i * j > n)break;//超过数据大小就退掉。shai[i * j] = 1;//1标记的都是素数的倍数——所以不是素数。}}}for (int i = 0; i < cnt; i++){printf("%d ", cun[i]);}
}

欧式筛选和埃式筛选

代码：

#include <bits/stdc++.h>
#define int __int128 //用__int128稳一点 
using namespace std;long long ans=0;
const int n=10000010;
bool f[10000010]={1,1}; //标记
vector<int> v;
signed main(){for(int i=2;i<=n;i++){if(f[i]!=1)  v.push_back(i);for(int j=0;j<v.size()&&v[j]*i<=n;j++){f[v[j]*i]=1;if(i%v[j]==0)break;}}
for(int i=0;i<v.size();i++)for(int j=i+1;j<v.size();j++){if(v[i]*v[i]*v[j]*v[j]<2333)continue;else  if(v[i]*v[i]*v[j]*v[j]>23333333333333)break;ans++;}cout<<ans<<endl; 
}