20241129-C07-数学专题（一）

原题链接：33673.徐沐瑶专属笔记C++

1943

2024-11-29 20:43:21

发布于：江苏

11阅读

0回复

0点赞

一. 素数

问题：如何判断一个数字是不是质数？

质数定义：只有1和它本身2个因数的数，最小的质数(素数)是2。

方法1：统计因数个数

int n, cnt = 0;	//count 表示因数的个数
cin >> n;
for (int i=1; i<=n; i++) {
	if (n%i == 0) {
		cnt++;
	}
}
if (cnt == 2) cout << "Yes";
else cout << "No";

方法2：试除法， 2到n-1之间不存在第3个因数

	bool flag = 1;	//假设是质数 
	int n;cin >> n;
	if (n < 2){
		flag = 0;	
	} 
	for (int i=2; i<=n/i; i++){
//	for (int i=2; i*i<=n; i++){
//	for (int i=2; i<=sqrt(n); i++){
//	for (int i=2; i<=n-1; i++){
		if (n%i==0){	//存在第3个因数， 一定不是质数 
			flag = 0;
			break; 
		} 
	}
	if (flag == 1)cout << "Yes"; 
	else cout << "No";

实例1:A325.打印质数表

参考程序：

int n;
cin>>n;
for (int i=2; i<=n; i++) {
	//判断i是不是质数	//枚举2 ~ i-1
	bool flag = 1;		//假设i是质数
	for (int j=2; j<=sqrt(i); j++) {
		if (i%j == 0) {
			flag = 0; 	//说明不是质数
		}
	}
	if (flag == 1) cout << i <<" ";
}

实例2:A30452.【PY】【for】聪明的乐乐

参考程序：

	int n, sum = 0, fac = 1;
	cin >> n;
	for (int i=1; i<=n; i++){
		if (n%i==0){
			sum += i;
			fac *= i; 
		}
	} 
	cout << sum << endl << fac << endl;

二. 最大公约数

实例: A7821.最大公约数

方法1: 枚举

	int n, m;
	cin >> n >> m;

	for (int i=n; i>=1; i--){
		if(n%i==0 && m%i==0){
			cout << i;
			return 0;
		} 
	}

方法2：辗转相除法(欧几里得)

	int n, m;
	cin >> n >> m;
	while (n%m != 0){
		int t = n; 
		n = m;				//除数变成了被除数 
		m = t%m; 			//余数变成了除数 
	}
	cout << m;				//当余数为0的时候,除数是gcd

三. 最小公倍数

实例：A30161.【循环】最小公倍数

#include <bits/stdc++.h>
using namespace std;

int n,m;

int main(){
	cin>>n>>m;
	for(int i=m; ;i+=m){
		if(i%n==0){
			cout<<i;
			return 0;
		}
	}	
	return 0;
}