241123-C04-数学专题+复习

原题链接：33265.笔记汇总

1943

2024-11-23 18:47:38

发布于：江苏

18阅读

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个因数

int n;
cin >> n;
if (n < 2) {
	cout << "No";
	return 0;
}
for (int i=2; i<=n/i; i++) {		//相对安全
//	for (int i=2; i*i<=n; i++){		//可能爆int
//	for (int i=2; i<=sqrt(n); i++){	//需要数学头文件
//	for (int i=2; i<=n-1; i++){		//循环次数较多
	if (n%i==0) {		//找到了除了1和它本身之外的第3个因数
		cout << "No";	//那么一定不是素数
		return 0;
	}
}
cout << "Yes";

实例1:A325.打印质数表

A. 非函数版

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 <<" ";
}

B. 函数版

//function作用，封装到函数中
//返回n是不是质数
//2.函数的定义
bool prime(int n) {		//形参
	if (n<2) return false;
	for (int i=2; i<=sqrt(n); i++)
		if (n%i == 0) return false;
	return true;
}

int main() {
	int n;
	cin >> n;
	for (int i=1; i<=n; i++) {
		if (prime(i) == 1) {		//3.函数的调用（实参）
			cout << i << ' ';
		}
	}
	return 0;
}

实例2:A491.质因数

bool prime(int n) {
	if(n<2) return 0;
	for (int i=2; i*i<=n; i++)
		if(n%i == 0) return 0;
	return 1;
}

int main() {
	int n;
	cin >> n;
	for (int i=n-1; i>=2; i--) {
		int a = i, b;
		if (n%i==0) b = n/i;		//保证b是一个整数
		else continue; 				//如果不是的, 继续下一个

		if (prime(a) && prime(b)) {
			cout << a;
			return 0;				//找到了则全部结束 
		}
	}
	return 0;
}

二. 最大公约数

实例: 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;
}