我要招人

去企业版

首页 > 试题广场 >

素数对

[编程题]素数对

热度指数：749 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请你找出满足 ${A + B = C^2}$ ，且 $A，B，C$ 均小于等于 ${N}$ 的素数三元组 ${(A, B, C)}$ 的数量。

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

输入描述:

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

输出描述:

一行中输出答案。

示例1

输入

输出

说明

算法知识视频讲解

Java

Sen🍓🍀

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Integer> list = new ArrayList<>(); // 素数表
        Set<Integer> set = new HashSet<>(); // 加快第三个数的查找
        for (int i = 1; i <= n; i++) {
            if (prime(i)) {
                list.add(i);
                set.add(i);
            }
        }

        int m = list.size(), res = 0;
        for (int i = 0; i < m; i++) { // 取AC/BC减少选择范围:
            for (int j = i; j < m; j++) { // C>=A
                int a = list.get(i), c = list.get(j);
                int b = c * c - a;
                if (b > list.get(m - 1)) break; // C*C-A=B<=MAX

                if (set.contains(b)) {
                    if (a != b) res += 2; // AB、BA
                    else res++;
                }
            }
        }
        System.out.println(res);
    }

    // 判断素数
    private static boolean prime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

发表于 2025-04-06 12:48:54 回复(0)

牛客52113612号

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // 1. 筛素数
        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 收集素数列表
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) primes.add(i);
        }

        int count = 0;
        // 2. 枚举 C
        for (int C : primes) {
            long target = (long) C * C;
            if (target > 2L * N) break;  // A+B = target, A,B ≤ N ⇒ target ≤ 2N

            // 3. 枚举 A
            for (int A : primes) {
                if (A > target) break;
                int B = (int) (target - A);
                if (B >= 2 && B <= N && isPrime[B]) {
                    count++;
                }
            }
        }

        System.out.println(count);
    }
}

发表于 2026-04-02 20:57:45 回复(0)

Python3

Djungelskog2026

import sys

n = int(sys.stdin.readline())

if n < 2:

print(0)

exit()

is_p, primes = [False]*2 + [True]*(n - 1), []

for i in range(2, n + 1):

if is_p[i]:

primes.append(i)

for j in range(i**2, n + 1, i):

is_p[j] = False

ans = 1 # a，b，c都等于2时成立，除这种情况外c必为奇数，此时a，b必有一个为2

for c in primes[1:]:

a = c**2 - 2

if a > n:

break

if is_p[a]:

ans += 2

print(ans)

发表于 2026-03-26 15:21:00 回复(0)

Aa_Bao

importsys

forline in sys.stdin:

a = line.split()

N = int(a[0])

ifN < 2:

print(0)

else:

# 埃拉托斯特尼筛法生成素数列表

is_prime = [True] * (N + 1)

is_prime[0] = is_prime[1] = False

fori in range(2, int(N**0.5) + 1):

ifis_prime[i]:

forj in range(i * i, N + 1, i):

is_prime[j] = False

# 初始化素数三元组的数量

count = 0

# 处理 C = 2的情况

ifis_prime[2]:

if2* 2<= 2* N:

ifis_prime[2]:

count += 1

# 处理 C 为奇数素数的情况

forC in range(3, N + 1, 2):

ifis_prime[C]:

square_C = C * C

ifsquare_C > 2* N:

break

# 考虑 A = 2的情况

B = square_C - 2

ifB <= N and is_prime[B]:

count += 2

# 输出结果

print(count)

发表于 2025-04-12 17:02:55 回复(0)

提交观点

问题信息

穷举数论

上传者：turnsoul

难度：

4条回答 16收藏 696浏览

素数对

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题