摘要：
对一个正整数分解质因数。
题目
描述
功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如 $180$ 的质因子为 $2$ $2$ $3$ $3$ $5$ ）
最后一个数后面也要有空格
输入描述：
输入一个long型整数
输出描述：
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。
示例1
输入：
180
输出：
2 2 3 3 5
最小质因子和最大质因子+埃式筛优化
一个显然的思路是，对于一个数，找到它的最小质因子，然后将这个数更新成对该最小质因子整除后的数，依次再去找到其最小质因子。
可以从2开始试，如果一个数会被2整除，这个数除2之后也可以被2整除，直到结束。那么这个数的质因子就全是2.
如果在中间某处不能被2整除了，说明这个数往后更新的时候均不可被2整除。这时候尝试可否整除3.
按照这个方法直到找到所有最小质因子。
现在考虑如何优化。
优化一：
首先看下最大质因子性质：
一个正整数的质因子，最多只有一个大于其平方根。
证明：假设有超过一个质因子大于其平方根，那么二者相乘一定大于该数。得证。
对于目标数字 $x$，根据这个性质，我们可以将可能出现的质因子限制在 $\sqrt x$及以内。再考虑剩余可能的最后一个大于 $\sqrt x$的质因子。
优化二：
因为求的是所有质因子，那么在找到每个质因子之后，我们都可以借助 筛质数 思想，将一部分非质数筛掉，在剩下的中找目标质因子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <bits/stdc++.h>
using namespace std;
unordered_map<long, bool> st;
inline void solve(long &n)
{
long i = 2L;
for (; i <= (long)sqrt(n); i++) {
for (; !st[i] && n % i == 0;) {
cout << i << ' ';
n /= i;
}
bool is_set = false;
if (!is_set) {
for (long j = i + i; j <= (long)sqrt(n); j += i)
st[j] = true;
is_set = true;
}
}
if (n != 1) cout << n << ' ' << endl;
}
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
long n;
for (; cin >> n;)
solve(n);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
for (; in.hasNext();) {
long x = in.nextLong();
Map<Long, Boolean> hash = new HashMap<>();
for (long i = 2; i <= (long)Math.sqrt(x); i++) {
boolean isSet = false;
for (;(hash.get(i) == null || hash.get(i) == false) && x % i == 0;) {
System.out.print(i + " ");
x /= i;
if (!isSet) {
for (long j = i + i; j <= (long)Math.sqrt(x); j += i) {
hash.put(j, true);
}
isSet = true;
}
}
}
if (x != 1) System.out.print(x + " ");
}
}
}
|