首页 > 试题广场 >

素数对

[编程题]素数对
  • 热度指数：756 时间限制：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}
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2026-03-12 15:22:16
素数对 思路 拿到这道题，我们要找满足 的素数三元组 ，其中 都是素数且都不超过 。注意 的顺序不同算不同的三元组。 首先想一个关键的约束：因为 ，，所以 ，也就是 ，即 。当 时， 最大也就到 左右。这意味着我们需要枚举的 的范围非常小！ 有了这个观察，算法就很直接了： 筛素数：用埃 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-16 15:32:55
题目链接 素数对 题目描述 请你找出满足 ，且 均为小于等于 的素数的三元组 的数量。 解题思路 1. 数学性质分析 我们来分析方程 ，其中 都是小于等于 的素数。核心在于利用素数的奇偶性。 情况一：C = 2 如果 （唯一的偶素数），那么 。方程变为 。 要使两个素数的和为 4，唯一 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

相关试题

素数对

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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