质因数分解

质数相乘

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。

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

int main(){
	int n;	//	分解的合数
	while(cin >> n){
		cout << "n = ";
		bool num_frist = true;	//判断是否为首个元素，用来控制乘号的输出 
		for(int i = 2; i <= n; i++){
			if(n %i ==0){
				if(!num_frist)
					cout << "*";
				num_frist = false;
				cout << i;
				n /= i;
				i--;	//i--是防止出现 如：24被2整除以后仍能够继续被2整除的 
			}
		}
		cout << endl;
	}
    return 0;
}

算数基本定理

任何一个大于1的自然数 $N$，如果$N$不为质数，都可以唯一分解成有限个质数的乘积$N=P_1^{a_1} P_2^{a_2} P_3^{a_3}…P_n^{a_n} $ ，这里 $P_1<P_2<P_3<…<P_n$均为质数，其诸指数 $a_i$是正整数。

这样的分解称为$N$ 的标准分解式。

以下将采用算数基本定理的标准分解式对数进行因式分解

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

int main(){
	int n;	//	分解的合数
	while(cin >> n) {
		cout << "n = ";
		bool num_frist = true;	//判断是否为首个元素，用来控制乘号的输出 
		for(int i = 2; i <= n; i++){	//从最小的质数开始 
			int a = 0;	//定义指数 
			while(n %i ==0){	//判断是否能够整除 
				n /= i;	//能整除将商留下继续 
				a++;	//指数++ 
			}
			if(a){
				if(!num_frist)	//控制乘号输出 
					cout << "*";
				num_frist = false;
				cout << a << "^" << i;
			}
		}
		cout << endl;
	}
    return 0;
}

而共有多少个约数：$(a_1+1)(a_2+1)…(a_n+1)$

欧拉数（小于$n$且与$n$互质的数的个数：

$phi(n)=n*(1-1/p_1)*(1-1/p_2)*...*(1-1/p_n)$;

求约数个数

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

int main(){
	int n;	//	分解的合数
	while(cin >> n) {
		cout << "n = ";
		int sum_d = 1;	//统计约数个数
		bool num_frist = true;	//判断是否为首个元素，用来控制乘号的输出 
		for(int i = 2; i <= n; i++){	//从最小的质数开始 
			int a = 0;	//定义指数 
			while(n %i ==0){	//判断是否能够整除 
				n /= i;	//能整除将商留下继续 
				a++;	//指数++ 
			}
			if(a){
				sum_d *= (a+1);	//满足条件的 a 进行计算
				if(!num_frist)	//控制乘号输出 
					cout << "*";
				num_frist = false;
				cout << a << "^" << i;
			}
		}
		cout << endl;
		printf("sum=%d\n",sum_d);
	}
    return 0;
}

欧拉数

筛选素数

此处将总结三种筛选素数的方法：

• 暴力枚举筛：$O(n*\ln{n})$
• 普通倍数筛：$O(n*\ln{n})$
• 线性筛：$O(n)$

暴力枚举筛

遍历$2$~$N$以内的所有数，随后判断这个数是否能被除$1$和自身以外的数整除

时间复杂度：$O(n*\sqrt{n})$

#include <bits/stdc++.h> using namespace std; const int N = 100100; int prime [N],cnt; int f1(int n){ //从2开始，依次枚举 for(int i=2; i <= n; i++){ bool flag = false;//状态判断 //找约数 最多找到 根号n for(int j = 2; j * j<= i; j++){ //若能整除，改变状态值 if(i % j == 0){ flag = true; break; } } //将标记出来的数存入数组 if(!flag) prime[cnt++] = i; } //打印 for(int i = 0; i <cnt; i++){ cout <<prime[i] << " "; } cout << endl; } int main(){ int n; while(cin >> n) f1(n); return 0; }

普通倍数筛

遍历$2$~$N$以内的所有数，从$2$开始遍历，在此同时对$N$以内中所有$2$的倍数进行一个状态标记。

时间复杂度：$O(n*\ln{n})$

例如：

• 2是质数，而4,6,8,10,12…则是合数，作标记
• 3是质数，而6,9,12,15…则是合数，做标记
• 4已经被做标记，则不再做标记
• 5是质数，而5,10，15,20,25…则是合数，做标记
• ……
• 依次遍历至$N$

#include <bits/stdc++.h> using namespace std; const int N = 1000100; int prime[N],cnt; bool st[N]; int f2(int n){ //从2开始，依次枚举 for(int i = 2; i <=n; i++){ //检查是否被标记 if(st[i])continue; prime[cnt++] = i; //未标记数字装入数组 //找倍数，标记其倍数。 //此处 i 已经装入了素数集合，则从2倍 i 开始遍历 for(int j = i + i; j <= n; j += i){ st[j] = true; } } //打印 for(int i = 0; i <cnt; i++){ cout <<prime[i] << " "; } cout << endl; } int main(){ int n; while(cin >> n) f2(n); return 0; }

线性筛法