质因数分解

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

近4年CSPJ考察情况：

难易度：中等

朴素试除法

判断一个数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;
}

可以理解为，墙从 x−1 的位置移动到了sqrt(x)的位置。

分解质因数

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

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

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

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;
}

历年真题

Coming soon 。。。