一、定义
因子：假如整数n除以m，结果是无余数的整数，那么我们称m就是n的因子。
质因子：在数论里，某一正整数的质因子指能整除该数的质数整数。
完数：一个数的因子之和等于它本身，则该数为完数。
二、性质
1、因子性质
无
2、质因子性质
两个没有共同质因子的正整数称为互质。
数字1与任何正整数（包括1 本身）都是互质。
This is because it has no prime factors; it is the empty product。
正整数的因数分解给出一连串的质因子；所有质因子相乘后。质因子如重复会以指数表示。
根据Fundamental theorem of arithmetic，任正整数有独一无二的质因子分解式。
设任正整数n，其质因子数目及其质因子的和是n的算术函数(arithmetic function)。
例子 6的质因子是3和2。(6 = 3 × 2) 5只有1个质因子，5本身。（5是质数。）
100有2个质因子：2和5。(100 = 2 x 50, 且100=5 x 20，只有2和5是质数)
2、4、8、16等只有1个质因子：2（2是质数，4 = 2 x 2，8 = 2 x 4，如此类推。偶数(6除外)的因子中，只有2是质数。）
1没有质因子。（1是empty product）
3、
三、定理
1、任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积 N=(P_1^a1)*(P_2^a2)......(P_n^an) , 这里P_1<P_2<...<P_n是质数，其诸方幂 ai 是正整数。
这样的分解称为N 的标准分解式。
2、对于任意的整型N，分解质因数得到N= P1^x1 * P2^x2* …… * Pn^xn;
则N的因子个数M为 M=（x1+1） * （x2+1） * …… *（xn+1）;
证明：
24 = 2^3 * 3^1；
其质因子有：为2和3 指数为 3和1
那么对于2 有0 1 2 3四种指数选择，对于3 有0 1两种指数选择
所以 就是4 * 2 = 8 个因子个数
如果还是不懂，那么我们就列举出来吧
2 3
2^0*3^0=1 2^0*3^1=3
2^1*3^0=2 2^1*3^1=6
2^2*3^0=4 2^2*3^1=12
2^3*3^0=8 2^3*3^1=24
结果很清晰了吧？？其实这里用到了数学的排列组合的知识
也就是说每一个质因子的不同指数幂与其它质因子相乘，得到的结果一定不会重复
因此能够将所有的因子都列举出来。
所以N的因子数M，我们可以用M=（x1+1） * （x2+1） * …… *（xn+1）表示
3、
四、判断是否是某个数的因子
假如整数n除以m，结果是无余数的整数，那么我们称m就是n的因子。
五、求因子及个数
1、朴素一般方法
枚举1-N，计数
C++版本一
void getFactors(int n){
int cnt=0;
for(int i=1;i<=n;i++){
if(n%i==0){
printf("%d ",i);
cnt++;
}
}
printf("\n%d\n",cnt);
} 2、简单优化方法
C++版本一
void getFactors(int n){
int cnt=0;
int q=sqrt(n);
int a[n];
for(int i=1;i<=q;i++){
if(n%i==0){
a[++cnt]=i;
if(i*i!=n)
a[++cnt]=n/i;
}
}
sort(a+1,a+cnt+1);
for(int i=1;i<=q;i++){
printf("%d ",a[i]);
}
printf("\n%d\n",cnt);
} JAVA版本一
/**
* 求一个数的因子,这里值的是正因子，包含1，但不包含本身。
* @param n 自然数
* @return 因子的个数
*/
public static int getFactors(int n){
int count = 0;
if(n == 0)
return count;
else if(n == 1 || n == 2){
System.out.println("n");
return ++count;
}
else{
//包含1
System.out.print(1+" ");
int l = (int) Math.sqrt(n);
for(int i = 2; i <= l; i++){
if(n % i == 0){
System.out.print(i+" ");
System.out.print(n/i+" ");
count += 2;
}
}
}
return count+1;
}
3、普通筛
for(int i=1; i<=maxm; i++){
for(int j=i; j<=maxm; j+=i)
fla[j]++;
} 4、线性筛
参考文章：https://blog.csdn.net/weixin_43272781/article/details/85058735
C++版本一
int D[M];
int pre[M];
bool prime[M];
D[1]=1;
prime[0]=prime[1]=1;
for(int i=2;i<M;i++){
if(!prime[i]){
D[i]=2;
pre[++cnt]=i;
}
for(int j=1;j<=cnt&&i*pre[j]<M;j++){
prime[i*pre[j]]=1;
D[i*pre[j]]=D[i]*2;
if(i%pre[j]==0){
int c=1;
t=i;
while(t%pre[j]==0){
t/=pre[j];
c++;
}
D[i*pre[j]]=D[t]*(c+1);
break;
}
}
//cout<<i<<" "<<D[i]<<endl;
}
六、求质因子及个数
C++版本一
#include<iostream>
#include<cstring>
using namespace std;
int main(){
long a;
int k=0;
int b[100];
cin>>a;
for(int i=2;i<=a;i++){
while(a%i==0){
a/=i;
b[k]=i;
k++;
}
}
for(int i=0;i<k;i++)
cout<<b[i]<<' ';
return 0;
}
JAVA版本一
/**
* 求一个自然数的质因子
* @param n 自然数
* @return 质因子个数
*/
public static int getFactorsByPrimeNumber(int n){
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(2);
int m = n;
if(n == 0 || n ==1)
return 0;
else{
if(Day1.isPrimeNumber(m)){
list.add(n);
System.out.print(n+"= 1*"+n);
return 1;
}else{
int curLast = 0;
while(!Day1.isPrimeNumber(m)){
curLast = list.getLast();
while(true){
if(Day1.isPrimeNumber(curLast)){
if(m % curLast == 0){
list.add(curLast);
m = m / curLast;
break;
}
}
curLast++;
}
}
list.add(m);
//打印输出
int valuse = list.get(1);
int count = 1;
System.out.print(n+"="+valuse);
for(int i = 2; i < list.size(); i++){
System.out.print("*"+list.get(i));
if(valuse != list.get(i)){
count++;
valuse = list.get(i);
}
}
return count;
}
}
}
七、求公因子及个数
1、公因子
定义：
设a,b是两个整数，若c是整数，且c整除a,则c称为a的一个因子（或约数），a的所有约数组成一个非空集合（设为A），b的所有因子组成集合B，设A∩B=C,称C的元素为a和b的公因子，显然C非空，因为至少1属于C。
如4和6的所有公因子为1,2，-1,-2
公因子都是以相反数形式成对出现的，所以一般研究正因子就够了。这样,4和6的公因子为1,2
JAVA版本一
/**
* 求两个数的公因子
* 思路：
* 1. 先求两个数的公约数
* 2. 对最大公约数进行求因子。如果该公约数为所求两个数较小的数，则公因子不包括该数，否则则包括
* 比如 30 15 最大公约数为15 公因子为 1 3 5
* 比如 20 8 最大公约数为4 公因子为 1 2 4
* @param n m 参数
* @return 公因子个数
*/
public static int getAllFactors(int n,int m){
int count = 0;
if(n ==0 || m ==0)
return 0;
else{
//调用最大公约数函数
int greatestCommonMeasure = Tools.getGreatestCommonMeasure_2(n, m);
if(greatestCommonMeasure == 0){
return greatestCommonMeasure;
}else if(greatestCommonMeasure == 1){
System.out.println(1+" ");
return greatestCommonMeasure;
}else{
System.out.print(1+" ");
count++;
if(greatestCommonMeasure != n && greatestCommonMeasure != m){
count++;
System.out.print(greatestCommonMeasure+" ");
}
int l = (int) Math.sqrt(greatestCommonMeasure);
for(int i = 2; i <= l; i++){
if(greatestCommonMeasure % i == 0){
System.out.print(i+" ");
System.out.print(greatestCommonMeasure/i+" ");
count += 2;
}
}
}
return count;
}
}
2、最大公因数
参考文章
https://blog.csdn.net/weixin_43272781/article/details/86547908
八、完数
1、判断
#include <iostream>
using namespace std;
int main()
{
int sum=0;
int n;
cin>>n;
for(int i=1; i<n; i++)//这里可以换成int i=1;i<=n/2;i=i+2
{
if(n%i==0)
{
sum=sum+i;
}
}
if(sum==n)
{
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}
}
2、区间内的完数
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
vector<int>a; //创建向量
for(int i=2; i<10000; i=i+2)//先把小于10000的完数找出来
{
int sum=1;
for(int j=2; j<=i/2; j++)
{
if(i%j==0)sum=sum+j;
}
if(sum==i)a.push_back(i);
}
int n;
cin>>n;
for(int i=1; i<=a.size(); i++)
{
if(a[i]<n) cout<<a[i]<<endl;
}
}
九、例题
https://codeforces.com/problemset/problem/236/B（题解：https://blog.csdn.net/weixin_43272781/article/details/86585021）
http://acm.hdu.edu.cn/showproblem.php?pid=5970
https://codeforces.com/problemset/problem/920/F（题解：https://blog.csdn.net/weixin_43272781/article/details/86584055）
十、参考文章
https://blog.csdn.net/u010794180/article/details/48860927
https://blog.csdn.net/weixin_43272781/article/details/86547908
https://blog.csdn.net/a1b2c3d4123456/article/details/50410028
https://blog.csdn.net/yanglong_blog_/article/details/75907154
京公网安备 11010502036488号