- 素因子(也称质因数/质因子):
在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式 。只有一个质因子的正整数为质数。
每个合数都可以写成几个质数（也可称为素数）相乘的形式，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数；而这个因数一定是一个质数。
质因数就是一个数的约数，并且是质数。
比如8=2×2×2，2就是8的质因数；
12=2×2×3，2和3就是12的质因数。
把一个式子以12=2×2×3的形式表示，叫做分解质因数。
把一个合数写成几个质数相乘的形式表示，这也是分解质因数 ，如16=2×2×2×2，2就是16的质因数。
把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。
分解质因数只针对合数。（分解质因数也称分解素因数）求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。
分解质因数的方法是先用一个合数的最小质因数去除这个合数，得出的数若是一个质数，就写成这个合数相乘形式；若是一个合数就继续按原来的方法，直至最后是一个质数 。
分解质因数的有两种表示方法，除了最常用的“短除分解法”之外，还有一种方法就是“塔形分解法”。
分解质因数对解决一些自然数和乘积的问题有很大的帮助，同时又为求最大公约数和最小公倍数做了重要的铺垫。
Pollard Rho因数分解
1975年，John M. Pollard提出了第二种因数分解的方法，Pollard Rho快速因数分解。该算法时间复杂度为。
分解质因数代码：
将一个正整数分解质因数。例如：输入90，打印出90=2×3×3×5。
程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
(2)如果n>k，但n能被k整除，则应打印出k的值，并用n除以k的商作为新的正整数n，重复执行第一步。
(3)如果n不能被k整除，则用k+1作为k的值，重复执行第一步。
-
因子： image.png
总结：
求素因子的时候，包含本身（如果本身是素数）
但是求因子和（用原始的迭代）不需要包含1和本身。
求最大的素因子：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int SIZE = 20002;
bool prim[SIZE + 1];
void get_prims() {
int SIZE_2 = SIZE + 1;
//true表示是素数, flase表示非素数
if (SIZE >= 2)
fill(prim + 2, prim + SIZE_2, 1);
for (int i = 2; i * i <= SIZE_2; i++) {
for (int j = 2; i * j <= SIZE_2; j++) {
prim[i * j] = false;
}
}
}
int f(int n) {
int maxm = -1;
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
if (prim[i]) {
maxm = max(i, maxm);
}
if (prim[n / i]) {
maxm = max(n / i, maxm);
}
}
}
return maxm;
}
void solve(int n) {
int m, ans, max_value = -1, max_index = 0;
get_prims();
for (int i = 0; i < n; i++) {
scanf("%d", &m);
ans = f(m);
if (max_value < ans) {
max_index = m;
max_value = ans;
}
}
printf("%d", max_index);
}
int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
solve(n);
return 0;
}
判断因子和(没有计算1和本身)：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int f(int n) {
int ans = 0;
for (int i = 2; i * i <= n; i++) {
if (n % i != 0) continue;
if (i * i == n) ans += i;
else ans += i + n / i;
}
return ans;
}
void solve(int n) {
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= n; j++) {
if (i == j) continue;
if (f(i) == j && f(j) == i) {
printf("%d %d\n", i, j);
}
}
}
}
int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
solve(n);
return 0;
}
