題目

分析

首先，我們如何找到雙子數？

1）找到所有質數滿足范圍內的質數（即至少質數^2<=23333333333333)

我們看見雙子數x的范圍2333<=x<=23333333333333，又因為
x = p2 × q2,所以 p 和 q 的取值不能太大。代碼中篩選出所有小于等于 5,000,000 的質數（這個范圍足夠覆蓋所有可能的組合）。
2）遍歷質數對
對于每一對不同的質數 p 和 q（假設 p < q），計算 p2 × q2，檢查是否在目標區間內。

最后我再介紹一下
介紹一下最高效的質數篩【埃拉托斯特尼篩法】

for (int i = 2; i <= sqrt(N); i++) {if (isprime[i] == 0) {//標記非質數為 1for (int j = i * i; j <= N; j += i)isprime[j] = 1;//這一步為埃拉托斯特尼篩法的核心步驟！}}

首先定義一個數組isprime[i]用于標記i是否為質數，不同的是，將非質數標記為1

為什么從i*i開始遍歷？
比i * i 更小的 i 的倍數（例如 2* i、3* i、…、(i-1)* i）已經被之前更小的質數標記過了。例如：

當 i=5 時，25=10 已經被 i=2 循環時標記。
35=15 已經被 i=3 循環時標記。
所以第一個未被標記的 i 的倍數是 i*i=25。

為什么j+=i而不是j++?
這一步的目的是按步長 i 遞增，標記所有 i 的倍數。

具體例子（以 i=5 為例）
初始時：i=5（且 i 是質數）。
標記起點：j = 5*5 = 25。
標記過程：
標記 25 為非質數 → j += 5 → 30。
標記 30 為非質數 → j += 5 → 35。
依此類推，直到 j 超過 N。

時間復雜度是 O(n log log n)，是效率最高的質數篩選算法之一！

代碼

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>#include <cctype>
using namespace std;
const int N = 5e6;
//為什么是5X10^6，因為x=p^2+q^2，當p=5e6已經能覆蓋所有可能的x范圍;
int isprime[N];int prime[N];
int main() {//開始篩2~N中的質數【遞推實現】for (int i = 2; i <= sqrt(N); i++) {if (isprime[i] == 0) {//標記非質數為 1for (int j = i * i; j <= N; j += i)isprime[j] = 1;//這一步為埃拉托斯特尼篩法的核心步驟！單獨見分析}}//收集所有質數到primeint cnt = 0;for (int i = 2; i <= N; i++) {if (isprime[i] != 1)prime[cnt++] = i;}int ans = 0;for (int i = 0; i < cnt; i++) {long long p2 = 1LL * prime[i] * prime[i]; //計算p^2if (p2 * p2 > 23333333333333)break;for (int j = i + 1; j < cnt; j++) {long long q2 = 1LL * prime[j] * prime[j];long long temp = q2 * p2;if (temp < 2333)continue;//結果小了，跳過本次循環，接著往后遍歷if (temp > 23333333333333)break;//結果打了，已經找到頭了，終止循環ans++;//如果滿足2333<=temp<=23333333333333，則記錄答案}}cout << ans << endl;return 0;
}