判断素数及分解质因数

Veröffentlicht am | in

如何判断一个数是否是素数

$O(\sqrt{n})$的朴素算法

自然，一个数是素数，则不应该存在一个数能整除它，而一个数$n$的所有因子都是关于$\sqrt{n}$对称分布的，所以只用检测$[1,\sqrt{n}]$的范围内是否有这个数的因子即可。

1
2
3
4
5
6
7
bool check(int n){
	if(n<=1)return 0;
	for(int i=1;i*i<=n;i++)
		if(n%i==0)
			return 0;
	return 1;
}

埃氏筛法

讲起来很麻烦，所以给个wiki的链接。
这是一个$O(nloglogn)$的算法，算是非常快的了（其实还能去掉一个log，不过效果不明显）
由埃氏筛法的想法，我们先去掉某个素数的倍数再来判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
bool isPrime[MAX_N];
int allPrime[MAX_N],tot=0;
void getPrime(){
	memset(isPrime,1,sizeof(isPrime));
	for(int i=2;i<MAX_N;i++){
		if(!isPrime[i])continue;
		allPrime[tot++]=i;
		for(int j=2*i;j<MAX_N;j+=i)
			isPrime[j]=0;
	}
}

米勒-拉宾素性检验

这是个很奇怪的算法，大家可以不学，此算法用的是一种概率的方式来猜测一个数是不是素数，一般不会出错。还是给个wiki的链接。
代码就不给出了

如何分解质因数

大家小学都学过短除法，现在就只需要用程序来模拟短除法的过程即可。
由于短除法需要遍历素数，所以先用埃氏筛法把素数存起来是很方便的。

1
2
3
4
5
6
7
8
9
10
11
int allFac[MAX_N],facNum=0;
void getFac(int x){
	while(x>1){
		if(x%allPrime[i]==0){
			x/=allPrime[i];
			allFac[facNum++]=allPrime[i];
		}
		else i++;
	}
}