性感素数
题目描述
“性感素数” 是指形如 $(p, p + 6)$ 这样的一对素数。
之所以叫这个名字,是因为拉丁语管 “六” 叫 “sex”(即英语的 “性感”)。
现给定一个整数,请你判断其是否为一个性感素数。
输入格式
输入在一行中给出一个正整数 $N$。
输出格式
若 $N$ 是一个性感素数,则在一行中输出 Yes
,并在第二行输出与 $N$ 配对的另一个性感素数(若这样的数不唯一,输出较小的那个)。
若 $N$ 不是性感素数,则在一行中输出 No
,然后在第二行输出大于 $N$ 的最小性感素数。
数据范围
$1 \le N \le 10 ^ 8$
输入样例 $1$:
47
输出样例 $1$:
Yes
41
输入样例 $2$:
21
输出样例 $2$:
No
23
正解
判断一个数是否是质数只需判断 $2 \sim \sqrt N$ 中是否有 $N$ 的因数即可,而不用去判断 $\sqrt N + 1 \sim N$。因为如果有一个大于 $\sqrt N$ 的 $N$ 的因数 $x$,那么令数 $y = \frac {N} {x}$,$y$ 也是 $N$ 的因数且 $y \lt \sqrt {N}$。然而 $y$ 已经被判过了,就没必要去判断 $x$ 了。
质数判断函数:
bool check (int x)
{
if (x <= 1)
{
return 0;
}
for (int i = 2; i * i <= x; i ++)
{
if (x % i == 0)
{
return 0;
}
}
return 1;
}
所以,如果一下 $N$ 和 $N - 6$ 都是质数,那么输出
Yes
n - 6
否则如果 $N$ 和 $N + 6$ 都是质数,输出
Yes
n + 6
否则将 $x$ 从 $N + 1$ 开始枚举,如果 $x$ 是质数且 $x - 6$ 或 $x + 6$ 是质数,就输出
No
x
否则就令 $x$ 增加 $1$,继续枚举。
AC Code
#include <iostream>
using namespace std;
int n;
bool check (int x)
{
if (x <= 1)
{
return 0;
}
for (int i = 2; i * i <= x; i ++)
{
if (x % i == 0)
{
return 0;
}
}
return 1;
}
int main ()
{
cin >> n;
if (check (n - 6) && check (n))
{
cout << "Yes\n" << n - 6;
}
else if (check (n) && check (n + 6))
{
cout << "Yes\n" << n + 6;
}
else
{
do
{
n ++;
}
while (!check (n) || !check (n - 6) && !check (n + 6));
cout << "No\n" << n;
}
return 0;
}
附送:Python3
代码
def check (x):
if x <= 1:
return False
for i in range (2, int (x ** 0.5) + 1):
if x % i == 0:
return False
return True
a = int (input ())
if check (a - 6) and check (a):
print ("Yes")
print (a - 6)
elif check (a) and check (a + 6):
print ("Yes")
print (a + 6)
else:
print ("No")
i = a
while not check (i) or not check (i - 6) and not check (i + 6):
i += 1
print (i)