目录

素数判断&约数枚举&整数分解（模板）素数判断基础版求素数 O(n)O(\sqrt{n})O(n​)代码进阶版求素数O((n)/3)O(\sqrt(n)/3)O((​n)/3)算法原理代码约数枚举代码1(纯C)代码2整数分解代码1代码2

素数判断&约数枚举&整数分解（模板）

素数判断

基础版求素数 O(n)O(\sqrt{n})O(n​)

一个写起来很快的算法，适用于绝大部分判断一个数是否是素数的题。

代码

int is_prime(long long m){long long i;for (i=2; i*i<=m; ++i){if (m%i==0) return 0;}return 1;}

进阶版求素数O((n)/3)O(\sqrt(n)/3)O((​n)/3)

但某些题O(sqrt(n))解决不了，需要更好的

算法原理

1.先看一个素数分布的规律：

大于等于5的素数，一定是出现在6的倍数的两侧（但是不代表在6的倍数的两侧的数一定是素数）。例如：5、7是素数，11、13也是素数，而25不是素数。

2.证明这个规律：

所有的大于等于5的数一定是{6x、6x+1、6x+2、6x+3、6x+4、6x+5}中的一个，其中6x+1和6x+5是在6的倍数的两侧。现在证明其他四个都不可能是素数。

证明：

6x、6x+2、6x+3、6x+4可以写成6x、2(3x+1)、3(2x+1)、2(3x+2)。显然他们都不是素数

代码

int is_prime(int n){long long i;if(n==1||n==4) return 0;if(n>=5){if(n%6==1||n%6==5){for(i=5;i*i<=n;i+=6)//采用了素数筛的思想（文章下半部分会介绍）{if(n%i==0||n%(i+2)==0) return 0;}}else return 0;}return 1;}

约数枚举

代码1(纯C)

int ar[MAXN];void divisor(int n){memset(ar,0,sizeof(ar));for(int j=1;j*j<=n;j++){if(n%j == 0) {ar[++ar[0]]=j;//ar[0]储存因子数目 if(n/j != j) {ar[++ar[0]]=n/j;}}}/*从小到大输出*/for(int j=1;j<=ar[0];j+=2)printf("%d ",ar[j]);for(int j=ar[0]/2*2;j>=2;j-=2)printf("%d ",ar[j]);printf("\n");}

代码2

vector<int> divisor(int n){vector<int> res;for(int i=1;i*i<=n;i++){if(n%i==0){res.push_back(i);if(i != n%1) res.push_back(i);}}return res;}

整数分解

代码1

int ar[MAXN][2];void prime_factor(int n){int i,j;memset(ar,0,sizeof(ar));for(i=2,j=0;i*i<=n;i++){if(n%i==0){ar[j][0]=i;//ar[j][1]++;do{ar[j][1]++;n/=i;}while(n%i==0);j++;}}if(n!=1) //这个n是质数{ar[j][0]=n;ar[j][1]=1;}}

代码2

map<int,int> prime_factor(int n){map<int,int> res;for(int i=2;i*i<=n;i++){while(n%i==0){++res[i];n/=i;}}if(n!=1) res[n]=1;return res;}