蓝桥杯 双子数

问题描述

若一个正整数 x 可以被表示为：

x = p² × q²

其中 p、q 为质数，且 p ≠ q，那么称 x 为一个双子数。

请计算在区间：

[2333, 23333333333333]

内有多少个双子数。

答案提交

这是一道结果填空题，你只需要算出结果后提交即可。

• 本题的结果为一个整数
• 在提交答案时只填写该整数
• 填写多余内容将无法得分

c++代码

#include<bits/stdc++.h>

using namespace std;

typedef __int128_t ll;

vector<bool> key;
vector<ll> primes;
long long ans = 0;

void getprime(ll n) {
    key = vector<bool>(n + 1, true);
    for (ll i = 2; i <= n; i++) {
        if (key[i]) primes.push_back(i);
        for (ll j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            key[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    /*
    ll n = sqrt(23333333333333);
    getprime(n);
    for (ll i = 0; i < primes.size(); i++) {
        ll k = primes[i] * primes[i];
        if (k > 23333333333333) break;
        for (ll j = i + 1; j < primes.size(); j++) {
            ll m = k * primes[j] * primes[j];
            if (m >= 2333 && m <= 23333333333333) ans++;
            if (m >= 23333333333333) break;
        }
    }
    cout << ans;
    */
    cout << "947293";
    return 0;
}//by wqs

这道题目long long也会溢出，使用

__int128_t