首页 > 试题广场 >

素数对

[编程题]素数对
  • 热度指数：750 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请你找出满足，且均小于等于的素数三元组  的数量。
素数三元组：A，B，C都是素数。

输入描述:
输入的第一行给出正整数。
{1 \leq N \leq 5 \times 10^5}


输出描述:
一行中输出答案。
示例1

输入

8

输出

3

说明

{2,2,2}
{7,2,3}
{2,7,3}
算法知识视频讲解
添加回答
Python3
Djungelskog2026头像 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)
提交观点

问题信息

穷举 数论
上传者：turnsoul
难度：
1条回答 702浏览

热门推荐

相关试题

素数对

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号