思路:素数筛 + 枚举优化

一个朴素的想法是:1.先得到n以内的素数 2.两重循环枚举$A+B$ , 判断是否是某个素数的平方。

对于第一步，$n = 5e5$ , 需要使用素数筛来加速这个过程。直接暴力判素数$O(n\sqrt{n})$会超时。可以使用埃式筛得到。

对于第二步，我们从第一步得到素数为$4e4$数量级。所以无法直接$O(p^2)$的作循环。但我们观察到这样的对其实很少！

因为$A+B = C^2$ , 那么也就要求$C$不能太大，$C = \sqrt{A+B} \leq \sqrt{2 * 4e4}=282$ 。 那么$[1,282]$ 内的素数就非常稀少了。

所以我们可以先用哈希$H$存储所有素数。然后先枚举$C$ , 再枚举$A$ 。然后再$H$ 中查找$B$的存在。

python

# Read the input
n = int(input())

# Sieve of Eratosthenes to find prime numbers up to n
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
primes = []
for i in range(2, n + 1):
    if is_prime[i]:
        primes.append(i)
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False

# Use a set for faster lookups
s = set(primes)

# Count the pairs
cnt = 0
for i in range(len(primes)):
    x = primes[i] ** 2
    if x >= primes[-1] * 2:
        break
    for j in range(len(primes)):
        y = x - primes[j]
        if y in s:
            cnt += 1
            break

# Print the count
print(cnt)

java

import java.util.*;
class Main{

   public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      boolean[] st = new boolean[n+1];
      List<Integer> list = new ArrayList<>(); // 素数
      for(int i = 2;i <= n;i++){
         if(st[i]) continue;
         list.add(i);
         for(int j = i;j <= n;j += i){
            st[j] = true;
         }
      }
      // C枚举，复杂度根号n
      int ans = 0;
      Set<Integer> set = new HashSet<>(list);
      for(int i = 0;i < list.size();i++){
         long total = 1L * list.get(i) * list.get(i);
         if(total > 1L * 2 * list.get(list.size()-1)){
            break;
         }
         for(int j = 0;j < list.size();j++){
            long diff = total - 1L * list.get(j);
            // System.out.println(total+" "+diff);
            if(set.contains((int)diff)){
               ans++;
            }
         }
      }
      System.out.println(ans);
   }
}

c++

#include <bits/stdc++.h>
#include<string>
using namespace std;
const int maxn=5e5+10;
typedef long long ll;
const ll inf=1e9+7;
const ll mod=1e9+7;
//线性筛
int prime[maxn];
bool vis[maxn];
map<int,bool>mp;
int tot;
void get_prime(int n){
	for(int i=2;i<=n;++i){
		if(!vis[i]){
			prime[++tot]=i;
			vis[i]=1;
			mp[i]=1;
		}
		for(int j=1;i*prime[j]<=n;++j){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	int N;
	cin>>N;
	get_prime(500000);
	int ans=0;
	set<int>::iterator it;
	for(int i=1;i<=tot;++i){
		int C=prime[i];
		if(C*C>N+1)break;
		for(int j=1;j<=tot;++j){
			int A=prime[j];
			if(A>=C*C)break;
			int B=C*C-A;
			if(mp[B])ans++;
		}
	}
	
	cout<<ans<<endl;
	return 0;
}

题目描述

小红希望你找出满足$A+B=C^2$,且A,B,C均小于等于N的素数三元组（A,B,C)的数量。

素数三元组：A,B,C都是素数。

输入描述

输入的第一行给出正整数N。

$1<=N<=5*10^5$

输出描述

一行中输出答案。

示例1

输入

8

输出

3

说明

2,2,2

7,2,3

2,7,3