详解c++质数、最大质因数与最小公倍数（最简单法）_c++求最大质因数

1.质数的定义

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。
文段采自：百度百科
了解更多：https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0/263515

2.判断质数

题目：输入一个正整数，判断其是否为质数，如果是，输出true；否则输出false
输入：输入只有一行，包含一个正整数n
输出：输出只有一行，为'true'或'false'
输入样例：5
输出样例: false
题目范围：1≤n≤10000
1
2
3
4
5
6

思路：用2到根号n之间的所有整数去除，均无法整除，则n为质数。
代码：

#include<iostream>
#include<cmath>
using namespace std;
int n;
bool js(int x)
{
	if(x==1)
		return false;
	if(x==2)
		return true;
	for(int i=2;i<=sqrt(x);i++)
		if(x%i==0)
			return false;
	return true;
}
int main()
{
	scanf("%d",&n);
	if(js(n))
		printf("true");
	else
		printf("false"); 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.最大质因数和最大公倍数

定义：如果一个正整数最大的质因数,它不能被其它正整数整除,那么我们称这个质因数为该数的最大质因数。
如：12的最大质因数为3,因为12的因数有1,2,3,4,6,12,其中最大的质数为3,所以3是12的最大质因数。

怎样求出：用最小的质数2去除这个数，除不尽的话就换成另一个比2大的最小质数，直至这个数为质数位置，这个数就是最大质因数
过程如下：

https://baike.baidu.com/pic/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0/6192375/0/838ba61ea8d3fd1f7d10e0fd304e251f94ca5fdf?fromModule=lemma_content-image&ct=single#aid=0&pic=838ba61ea8d3fd1f7d10e0fd304e251f94ca5fdf

题目：给出一个正整数n,求它的最大质因数是多少
输入：输入只有一行，包含一个正整数n
输出：输出只有一行，为一个正整数
输入样例：21
输出样例: 7
题目范围：1≤n≤10000

这个题目只需要用刚刚用过的判断质数的函数,再加上一个判断是否为n的因数即可
代码：

#include<iostream>
#include<cmath>
using namespace std;
int n;
bool js(int x)
{
	if(x<=1)
		return -1;
	for(int i=2;i<=sqrt(x);i++)
		if(x%i==0)
			return false;
	return true;
}
int jjs(int x)
{
	int maxx;
	for(int i=2;i<=x;i++)
		if(x%i==0 && js(x/i))
			maxx=max(maxx,x/i);
	return maxx;
}
int main()
{
	scanf("%d",&n);
	printf("%d",jjs(n)); 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

既然讲到了最大质因数，那也就顺便将最大公倍数也讲一下

定义：几个数共有的倍数叫做这几个数的公倍数，其中除0以外最小的一个公倍数，叫做这几个数的最小公倍数。
例如：12与15的最小公倍数为60,13与5的最小公倍数为65
了解更多：https://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0/6192375

在数学中求与最大质因数基本相同，除去的质数乘上最底下的质数就是最小公倍数

图片来源：百度百科 https://baike.baidu.com/pic/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0/6192375/0/838ba61ea8d3fd1f7d10e0fd304e251f94ca5fdf?fromModule=lemma_content-image&ct=single#aid=0&pic=838ba61ea8d3fd1f7d10e0fd304e251f94ca5fdf

题目：给出两个数n与m，求这两个数的最小公倍数是多少
输入：输入只有一行，包含两个正整数n和m，中间用一个空格隔开
输出：输出只有一行，为一个正整数，没有则输出-1
输入样例：12 15
输出样例: 60
题目范围：1≤n,m≤500

思路：使用模拟法，用ans代替除去的质数，用sum代替除去的质数的积，将除去剩下的质数n与m与sun相乘的最小公倍数
代码：

#include<iostream>
#include<cmath>
using namespace std;
int i,n,m,sum=1,ans=2;
bool js(int x)
{
	for(int i=2;i<=sqrt(x);i++)
		if(x%i==0)
			return false;
	return true;
}
int main()
{
	scanf("%d %d",&n,&m);
	if(n==0 || m==0)
	{
		printf("-1");
		return 0;
	}//如果n或m为0，输出-1 
	if(js(n) && js(m) || js(n) && !js(m) || !js(n) && js(m))
	{
		printf("%d",n*m);
		return 0;
	} //如果两个数都为质数
	  //或一个为合数一个为质数 
	  //输出n*m 
	if(n%m==0)
	{
		printf("%d",n);
		return 0;
	}
	if(m%n==0)
	{
		printf("%d",m);
		return 0;
	}
	while(!js(n) && !js(m)) 
	{
		if(n%ans==0 && m%ans==0)
		{
			n/=ans,m/=ans;
			sum*=ans;
		}
		else
			for(i=1;;i++)
				if(js(ans+i))
				{
					ans+=i;
					break;
				}
	}
	printf("%d",sum*n*m);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

4.总结

质数、最大质因数和最小公倍数在我印象里是小学的知识了，不难，勤动脑就行。