一、定义

1.约数和倍数的定义：

a能被b整除就说明a是b的约数，b是a的倍数。

2.质数和合数的定义：

质数和合数是大于1的整数，如果只包含1和本身两个约数叫做质数，不然就叫做合数。

二、质数判断方法（时间复杂度的进化）

1.质数的判断方法：

方法一：线性判断质数

枚举2~n-1的所有数字一个个除n，如果都没余数则为质数，不然即是合数。

示例代码

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

时间复杂度：O(n)

方法二：对半判断质数

根据的性质：若n%i==0那么n%(n/i)==0

由此，我们可以得出要判断质数只要列举较小的数字就行，由此得出代码：

bool is_prime(int n) {
	if (n < 2) return 0;
	for (int i=2; i<=n/i; i++) {  // 写 i<=sqrt(n)也可以，但是还需要算，比较慢。
		if (n%i == 0) return 0;
	}
	return 1;
}

时间复杂度：O(log(n))

由此其得到了进化：由O(n) ————> O(log(n))

质数筛（一个可以快速筛出质数的东西）：

在需要多次判断质数时 我们就要使用时间复杂度更低的质数筛了

其分为朴素筛、埃氏筛、欧拉筛(线性筛)三大筛（时间复杂度从高到低）

1.朴素筛

const int N = 1e6+5;
int primes[N], cnt;  // primes用来存储质数，cnt是对应数组的下标
bool st[N];  // st[i]标记数字是否被筛掉

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
			if (!st[i]) {
				primes[++cnt] = i;  // 质数存到数组中
		}
		for (int j=i+i; j<=n; j+=i) st[j] = 1;  // 筛掉数字的倍数
	}
	// 这样过完之后，所有的质数就存到了primes数组中
	// 同时 st 中标记了每个数字是否是质数。
}

2.埃氏筛

const int N = 1e6+5;
int primes[N], cnt;  // primes用来存储质数，cnt是对应数组的下标
bool st[N];  // st[i]标记数字是否被筛掉

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
		if (!st[i]) {
			primes[++cnt] = i;  // 质数存到数组中
			for (int j=i+i; j<=n; j+=i) st[j] = 1;  // 筛掉质数的倍数
		}
	}
	// 这样过完之后，所有的质数就存到了primes数组中
	// 同时 st 中标记了每个数字是否是质数。
}

3.欧拉筛(线性筛)

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
		if (!st[i]) primes[++cnt] = i;  // 质数存到数组中
			// primes[j] <= n/i 理解为 primes[j]*i <= n，即只筛n范围内的数字
			for (int j=1; primes[j]<=n/i; j++) {
				st[primes[j]*i] = 1;  // 筛掉i的素数倍数
				if (i%primes[j] == 0) break;  // 线性复杂度的关键
			}
	}
}

三、枚举约数

方法一：线性枚举

const int N = 1e5+5;
int res[N], cnt;

void get_divisors(int n) {
	for (int i=1; i<=n; i++) {
		if (n%i == 0) res[++cnt] = i;
	}
}

对半枚举

const int N = 1e5+5;
int res[N], cnt;

void get_divisors(int n) {
	for (int i=1; i<=n/i; i++) {
		if (n%i == 0) {
			res[++cnt] = i;
			if (i != n/i) res[++cnt] = n/i;  // 这个判断是防止加两次 n/i 进去
		}
	}
	sort(res+1, res+1+cnt);  // 如果不要求排序，也可以不用。
	// 另外，也可以用两个数组，一个存前半部分一个存后半部分，最后合并，比排序更快。
}

快速幂

思想：通过幂次的二进制拆解，将幂次逐步减少，其时间复杂度从普通幂的O（b）降低到O（logb）.

THE END