题解：SP10818 FACTCG2 - Medium Factorization

题目意思：

给定一个整数

n\ (1\le n\le 10^7)

，分解质因数，用 x 隔开。

分解质因数板子题。

分解方法：

我们先用筛法筛出

1 \sim 10^7

所有的质数。

如果您不会质数筛，您可以看一下

质数筛筛法（接下来将默认有

n

个数）：

暴力枚举：

原理：从

1

到

n

依次枚举每一个数，每个数对从

2

到

\sqrt{n}

的数进行取模运算。

这里为什么是

\sqrt{n}

而不是

n

？

\ge \sqrt{n}

的数都可以由

n

除以一个小于

\sqrt{n}

的数得到，所以为了避免重复计算，减小时间复杂度，这里是

\sqrt{n}

而不是

n

。

缺点：时间复杂度为

\Theta(n \times \sqrt{n})

，遇到大数据会 TLE。

代码：

CPP

bool prime(int a) { // 只会返回 0 或 1
	// 特判部分
	if (a == 1) return 0; // 非质数
	if (a == 2) return 1; // 质数
	if (a == 3) return 1; // 质数
	// return 自带结束功能，不会进行下方操作
	for (int i = 2; i <= sqrt(a); i++) { // 依次对 2~sqrt(a) 取模
		if (a % i == 0) { // 能被非 1 和自身整除，说明是合数
			return 0;// 非质数
		}
	}
	return 1;// 检查完之后仍然没有判断为非质数，说明这个数是质数
}

埃氏筛法：

原理：每次检测到质数后把所有此质数的倍数由质数区转移到非质数区，最后输出所有质数区的数。

缺点：有些数可能会被转移至非质数区多次，时间复杂度为

\Theta(n \times log_2(log_2n))

，时间复杂度较暴力枚举有所优化，但仍有更优方法。

代码：

CPP

bool prime[n + 1];//预处理n范围内的素数，prime[i] = 1表示i是素数
void InitPrime() {
	int i, j; //初始化数组
	for (i = 0; i <= n; i++) prime[i] = 1; //规定0和1不是质数
	prime[0] = prime[1] = 0; //筛质数
	for (i = 2; i <= n; i++) { //如果i是质数
		if (prime[i]) { //把i的倍数都标记为不是质数
			for (j = i * 2; j <= n; j += i) prime[j] = 0;
		}
	}
}

欧拉筛法：

原理：在埃氏筛法的基础上，我们可以避免重复被转移的数，例如：

$35$ 既被筛 $5$ 的倍数时筛掉，又被筛 $7$ 的倍数时筛掉。

此时时间复杂度为

\Theta(n)

。

代码：

CPP

bool prime[n + 1];//预处理n范围内的素数，prime[i] = 1表示i是素数
vector<int> p;//存放范围内所有素数  p.size() = 素数个数
void InitPrime() {
	//初始化
	for (int i = 0; i <= n; i++) prime[i] = 1;
	prime[0] = prime[1] = 0;
	p.clear();
	//注意优化后的 i * i <= n 和 j = i * i 开始
	for (int i = 2; i * i <= n; i++)
		if (prime[i])
			for (int j = i * i; j <= n; j += i) prime[j] = 0;
	//也可将所有的质数存放进vector中方便使用，例如p.size() = n范围内素数的个数
	for (int i = 0; i <= n; i++) {
		if (prime[i]) p.push_back(i);
	}
}

然后读题，发现要在输出的最前端加上 1x，所以我们输出即可。

然后是分解质因数。

如果您不会分解质因数，您可以看一下

原理：用

n

模刚才找到的从小到大的质数，从

1

开始。用得数不断模这个数，知道不能继续整除为止。接着将模数指向下一个质数，直到它本身也变成了一个质数。

代码：

CPP

int *factorize(int num, int len) {
  int *result = (int *)malloc(len * sizeof(int));
  int i = 2;
  int result_idx = 0;
  while (i * i <= num) {
    while (num % i == 0) {
      result[result_idx] = i;
      num /= i;
      result_idx++;
    }
    i++;
  }
  if (num > 1) {
    result[result_idx]  = num;
  }
  return result;
}

最终代码：

CPP

#include<bits/stdc++.h>
using namespace std;
bool ip[10000005];
int p[1000005], t;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n = 10000000, i, j;
	ip[0] = ip[1] = true;
	for (i = 2; i <= n; i++) {
		if (!ip[i]) p[++t] = i;
		for (j = 1; p[j]*i <= n && j <= t; j++) {
			ip[i * p[j]] = true;
			if (i % p[j] == 0)
				break;
		}
	}
	while (cin >> n) {
		printf("1");
		if (n == 1) goto next;
		for (i = 1; p[i]*p[i] <= n; i++) // sqrt 是一个函数，如果使用有可能会 TLE
			while (n % p[i] == 0)
				n /= p[i], printf(" x %d", p[i]);
		if (n > 1) printf(" x %d", n);
next:
		printf("\n");
	}
	return 0;
}

题解：SP10818 FACTCG2 - Medium Factorization

文章操作

相关推荐

评论

题解：SP10818 FACTCG2 - Medium Factorization