函数
2
质数与最大公约数（题解）
做题网站：
1.
l
i
useroj.cc
（
内网穿透故障，
暂不可用）
2.
st.cpolar.cn
（
常用）
3.
tctm.cpolar.cn
（备用
1
）
4.
ykj.cpolar.cn
（
备用
2
）
前情概要：
一、
判断素数的方法：
1.
朴素算法
i
nt
j
udge(int
n)//
返回值
1
代表是质数
0
则不是
{
i
nt
i
;
i
f(n<=1)
return(0);//1
和
0
都不是质数
for(i=2;i<=n-1;i++)
i
f(n%i==0)
return(0);//
若
2
到
n-1
之间有能被整除的
则不是质数
return(1);
//
都不能整除
则是质数
}
时间复杂度：
O
（
N
）
较大，
不建议用。
2.
开方优化
i
nt
j
udge(int
n)//
返回值
1
代表是质数
0
则不是
{
i
nt
i
;
i
f(n<=1)
return(0);//1
和
0
都不是质数
for(i=2;i<=
i
nt(sqrt(n))
;
i
++)
i
f(n%i==0)
return(0);//
若
2
到
n-1
之间有能被整除的
则不是质数
return(1);
//
都不能整除
则是质数
}
时间复杂度：
O
（
√n
)
常用
二、
最大公约数与最小公倍数
1.
朴素算法求最大公约数：
以
n,m
为例
i
nt
x=min(n,m);
for(int
i
=x;i>0;i--)
i
f(n%i==0&&m%i==0)
break;
i
即为所求最大公约数。
时间复杂度：
O
（
N
）
较大，
不建议用。
2.
辗转相除法
i
nt
gcd(int
x,int
y)
{
i
f(x%y==0)
return(y);
return(gcd(y,x%y));
}
gcd(n,m)
即为所求最大公约数。
时间复杂度：
O
（
l
ogN
）
常用
3.
更相减损法
（
了解即可）
最小公倍数即为：
nm/gcd(n,m)
三、
逆序数构造（考察数位分离）
i
nt
NX(int
x)
{
i
nt
t=x,k,m=0;
while(t>0)
{
k=t%10;//
取个位
m=m10+k;//
合成新数
t=t/10;
}
return(m);
}
NX(n)
的值即为
n
的逆序数，
若要判断是否为回文数，
则额外判断
n
是否等于
NX(n)
即可。
时间复杂度：
O
（
|
n
|
）
即
n
的长度。
常用
题解：
A.
直接输入
x
判断
x
是否为质数，
按照题目要求输出即可。
B.
回文质数，
先判断是否回文，
再判断该数是否为质数即可。（因回文数判断效率比质数判
断快，
所以必须先判断回文，
否则会超时）
C.
题目概述：
对于大于
5
的任意正整数，
至少有一种方案可以分解为两个质数的和。
令
i
从
2
循环到
n-2
，
判断
i
和
(n-i)
是否为质数，
若是，
则输出
i
和
(n-i)
，
并结束循环。
D.
题目概述：
对于大于
3
的任意正整数，
至少有一种方案可以分解为两个质数的和，
输出
i
(n-i)
的最大值。
因要求是最大值，
根据数论，
当
i
越接近
n/2
时，
乘积越大。
令
i
从
n/2
循环到
2,
判断
i
和
(
n-i)
是否为质数，
若是，
则输出
i
(n-i)
，
并结束循环。
E.
与
B
题类似，
不复赘述。
F.
题目概述：
已知
n
是两个质数的乘积，
输出较大的质数。
本题的陷阱在于，
若循环从
n
循环到
√n
，
直接求最大质数会因
n
值较大而超时。
换个思路：
既然
n
必是两个质数的乘积，可以先求出较小的那个质数
i
，
再输出
n/i
即可。
（
i
只需要从
2
循环到
√n
）
。
G.
题目概述：
将
n
拆解成为多个质数的乘积，
例如：
60=223*5
循环拆解即可，
拆到
n
本身成为质数，
则循环结束。
H.
结合质数判定和逆序数构造即可。
I
.
同
H
题。
J
.
类似
F
题。
K.
类似
A
题。
L.
类似
A
题。
M.
用辗转相除法即可。
N.
同
M
题。
O.
暴力模拟即可。
P.
提醒：
题目卡常数，
gcd
必须用
i
nt
类型。
因
x
必然是
b1
的因数，
可以考虑开方优化，
查
x
的同时，
共 31 条回复
函数 2 质数与最大公约数（题解） 做题网站： 1. l i useroj.cc （ 内网穿透故障， 暂不可用） 2. st.cpolar.cn （ 常用） 3. tctm.cpolar.cn （备用 1 ） 4. ykj.cpolar.cn （ 备用 2 ） 前情概要： 一、 判断素数的方法： 1. 朴素算法 i nt j udge(int n)// 返回值 1 代表是质数 0 则不是 { i nt i ; i f(n<=1) return(0);//1 和 0 都不是质数 for(i=2;i<=n-1;i++) i f(n%i==0) return(0);// 若 2 到 n-1 之间有能被整除的 则不是质数 return(1); // 都不能整除 则是质数 } 时间复杂度： O （ N ） 较大， 不建议用。 2. 开方优化 i nt j udge(int n)// 返回值 1 代表是质数 0 则不是 { i nt i ; i f(n<=1) return(0);//1 和 0 都不是质数 for(i=2;i<= i nt(sqrt(n)) ; i ++) i f(n%i==0) return(0);// 若 2 到 n-1 之间有能被整除的 则不是质数 return(1); // 都不能整除 则是质数 } 时间复杂度： O （ √n ) 常用 二、 最大公约数与最小公倍数 1. 朴素算法求最大公约数： 以 n,m 为例 i nt x=min(n,m); for(int i =x;i>0;i--) i f(n%i==0&&m%i==0) break;
i 即为所求最大公约数。 时间复杂度： O （ N ） 较大， 不建议用。 2. 辗转相除法 i nt gcd(int x,int y) { i f(x%y==0) return(y); return(gcd(y,x%y)); } gcd(n,m) 即为所求最大公约数。 时间复杂度： O （ l ogN ） 常用 3. 更相减损法 （ 了解即可） 最小公倍数即为： nm/gcd(n,m) 三、 逆序数构造（考察数位分离） i nt NX(int x) { i nt t=x,k,m=0; while(t>0) { k=t%10;// 取个位 m=m10+k;// 合成新数 t=t/10; } return(m); } NX(n) 的值即为 n 的逆序数， 若要判断是否为回文数， 则额外判断 n 是否等于 NX(n) 即可。 时间复杂度： O （ | n | ） 即 n 的长度。 常用 题解： A. 直接输入 x 判断 x 是否为质数， 按照题目要求输出即可。 B. 回文质数， 先判断是否回文， 再判断该数是否为质数即可。（因回文数判断效率比质数判 断快， 所以必须先判断回文， 否则会超时） C. 题目概述： 对于大于 5 的任意正整数， 至少有一种方案可以分解为两个质数的和。 令 i 从 2 循环到 n-2 ， 判断 i 和 (n-i) 是否为质数， 若是， 则输出 i 和 (n-i) ， 并结束循环。 D. 题目概述： 对于大于 3 的任意正整数， 至少有一种方案可以分解为两个质数的和， 输出 i (n-i) 的最大值。 因要求是最大值， 根据数论， 当 i 越接近 n/2 时， 乘积越大。 令 i 从 n/2 循环到 2, 判断 i 和 ( n-i) 是否为质数， 若是， 则输出 i (n-i) ， 并结束循环。 E. 与 B 题类似， 不复赘述。 F. 题目概述： 已知 n 是两个质数的乘积， 输出较大的质数。 本题的陷阱在于， 若循环从 n 循环到 √n ， 直接求最大质数会因 n 值较大而超时。 换个思路： 既然 n 必是两个质数的乘积，可以先求出较小的那个质数 i ， 再输出 n/i 即可。 （ i 只需要从 2 循环到 √n ） 。 G. 题目概述： 将 n 拆解成为多个质数的乘积， 例如： 60=223*5
循环拆解即可， 拆到 n 本身成为质数， 则循环结束。 H. 结合质数判定和逆序数构造即可。 I . 同 H 题。 J . 类似 F 题。 K. 类似 A 题。 L. 类似 A 题。 M. 用辗转相除法即可。 N. 同 M 题。 O. 暴力模拟即可。 P. 提醒： 题目卡常数， gcd 必须用 i nt 类型。 因 x 必然是 b1 的因数， 可以考虑开方优化， 查 x 的同时，
链接: https://pan.baidu.com/s/16RHcu1xhOhoYhT0aoKeLTQ 提取码: dgx7 函数2题解
int gcd(int n,int m) { if(n%m==0) return(m);
}//最大公约数
顶
@novice 张老师得了MVP
666
必须置顶
MVP
ceil(1.1) = 2 向上取整 floor(1.9) = 1 向下取整 round(1.5) = 2 四舍五入 以上三个头文件包含在头文件cmath