526互联

试除法判断质数和分解质因数

发布时间 2023-11-29 08:08:16作者: 陆留生信奥艺术

试除法和质因数分解是一个必须必须要掌握的知识点。因为其算法想法简单，但是考察确很多。究其原因，数论的内容一旦考察深了，就过难，容易没有区分度，比如2021年的筛法考察，那个题目绝大多数考生都是干瞪眼，题是很好，区分度不足。而质因数分解的难度就刚好，而且还可以和其他各种算法做结合。务必会写。

朴素试除法

判断一个数x是否是质数（很多时候称为素性测试），最简单的方法是试除法。试除，就是用2,3,...,x−1这些数字尝试整除x。只要其中有一个数能整除x，就说明x是合数，反之是质数。

// 写成函数形式的试除法，若为合数函数返回0，为质数函数返回1
bool isPrime(int x)

{
　　if (x < 2) return 0;
　　for (int i = 2; i < x; i++)

　　{

　　　　if (x % i == 0) return 0;
　　}
　　return 1;
}

试除法(优化后)

程序的过程，就像在数轴x−1的位置建了一堵墙，i从2开始不断右移到这堵“墙”，每次都要进行x%i的计算，若结果为0，说明i是x的因数，x是合数。

优化上面的方法，不需要试验到x-1，而只需要试验到sqrt(x)。​。时间复杂度也随之变为O(sqrt(x​))。

// 优化后的试除法
bool isPrime(long long x)

{
　　if (x < 2) return 0;
　　// 将 i < x 优化为 i * i <= x
　　for (long long i = 2; i * i <= x; i++)

　　{
　　　　if (x % i == 0) return 0;
　　}
　　return 1;
}

分解质因数

给定一个正整数，找到它的所有因数。

考虑朴素算法，因数是成对分布的，N 的所有因数可以被分成两块，即 [2,N​] 和[N​+1,N)。只需要把 [2,N​] 里的数遍历一遍，再根据除法就可以找出至少两个因数了。这个方法的时间复杂度为O(sqrt(N))。

最简单的算法即为从 [2,sqrt(N)]进行遍历。

cpp
vector <int> breakdown(int x) 

{

	vector <int> res;

	for (int i = 1; i <= x; i++) {

		if (x % i == 0) {

			while (x % i == 0) x /= i;

			res.push_back(i);

		}

	}

	if (x != 1) res.push_back(x);

	return res;

}