蓝桥杯备战4.双子数

P9420 [蓝桥杯 2023 国 B] 子 2023 / 双子数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

筛素数

void get_prime(int n)
{
    for(int i=1;i<=n;i++)
    {
        if(!st[i])prime[cnt++]=i;
    
        for(int j=0;prime[j]<n/i;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }
}

解题

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e7+10,M = 1e3+5;
int prime[N],cnt;
bool st[N];
void get_prime(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!st[i])prime[cnt++]=i;
		for(int j=0;prime[j]<n/i;j++)
		{
			st[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
signed main()
{
	std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	get_prime(1e7);
	int l=2333,r=23333333333333,ans = 0;
	for(int i=0;i<cnt;i++)
	{
		for(int j=i+1;j<cnt;j++)
		{
			int p1=prime[i],p2=prime[j];
			if(p1*p1*p2*p2<l)continue;
			if(p1*p1*p2*p2>r)break;
			ans++;
		}
	}
	cout<<ans;
	return 0;
}