[蓝桥杯 2023 国 B] 双子数
试题 B: 双子数
【问题描述】
若一个正整数 x x x 可以被表示为 p 2 × q 2 p^2 \times q^2 p2×q2,其中 p p p、 q q q 为质数且 p ≠ q p \neq q p=q,则 x x x 是
一个 “双子数”。请计算区间 [ 2333 , 23333333333333 ] [2333, 23333333333333] [2333,23333333333333] 内有多少个 “双子数”?
埃氏筛+暴力枚举
#include <bits/stdc++.h>
using namespace std;
int main()
{int d=sqrt(23333333333333);cout<<d<<endl; //4830458vector<__int128> a;vector<bool> st(5000010); st[0]=st[1]=1;for(int i=2;i<=5000000;i++){if(st[i]==0) a.push_back(i);for(int j=0;j<a.size()&&a[j]*i<=5000000;j++){st[a[j]*i]=true;if(i%a[j]==0) break;}}int ans=0; for(int i=0;i<a.size();i++)for(int j=i+1;j<a.size();j++){if(a[i]*a[i]*a[j]*a[j]<2333) continue;if(a[i]*a[i]*a[j]*a[j]>23333333333333) break;ans++;}cout<<ans;//947293 return 0;
}