首页 > 试题广场 >

素数对

[编程题]素数对
  • 热度指数：1311 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个正整数 N，我们称有序三元组 (A,B,C) 为素数三元组，当且仅当满足下述两条：
\hspace{23pt}\bullet\, A,B,C 均为素数；
\hspace{23pt}\bullet\, A+B=C^2。

\hspace{15pt}请你计算，不超过 N 的素数中，一共有多少个不同的素数三元组 (A,B,C) 满足上式。

输入描述:
\hspace{15pt}在一行上输入一个整数 N\left(1\leqq N\leqq 5\times10^5\right)。


输出描述:
\hspace{15pt}输出一个整数，代表满足条件的三元组数量。
示例1

输入

8

输出

3

说明

\hspace{23pt}\bullet\, 当 N=8 时，可选素数为 2,3,5,7： 
\hspace{38pt}\circ\, (2,2,2)：2+2=4=2^2； 
\hspace{38pt}\circ\, (7,2,3)：7+2=9=3^2； 
\hspace{38pt}\circ\, (2,7,3)：2+7=9=3^2； 
\hspace{23pt}共 3 组。
示例2

输入

5

输出

1

说明

\hspace{23pt}\bullet\, 当 N=5 时，可选素数仅 2,3,5：只有 (2,2,2) 满足条件，因此答案为 1。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 63浏览

热门推荐

相关试题

素数对

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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