C++，如何快速的求一个正整数的所有因数的个数？-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++，如何快速的求一个正整数的所有因数的个数？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

首先，让我们看看什么是因数，

定义：因数是指整数a除以整数b(b≠0) 的商正好是整数而没有余数，我们就说b是a的因数。

好，接下来是问题：

题目描述

给定一个整数n（1<<n<<10^9），求出n的因子的个数。

首先我们先看一看数据范围。

在C++中，整形（int）的数据范围在 -2^31~ 2^31-1 ，正数部分大概就是比2*10^9略大一些；

而长整形（long long）的数据范围在-2^63~ 2^63-1,正数部分大概就是比2*10^19略小一些；因此这一题中我们可以定义一个整型变量n；

接下来继续往下看，谈到因数，我们不得不想到“质数”（即“素数”，该数只有1和该数本身两个正因数），而当一个数,设为n，不是质数时，必然存在两个约数，设为a,b；其中有 a>=sqrt(n)，b<sqrt(n）；

继而可以知道n的因数的分布关系。

则接下来就有思路了。请看如下代码：

#include<bits/stdc++.h>
using namespace std;
int n；
int js(int x){
    int ans=0;  //计数器
    for(int i=1;i*i<=x;i++){  //循环到sqrt(x),不用函数，可以快一点；
        if(x%i==0){   // i 是x的因数；
            ans++;
            if(i!=x/i){ //特判一下，看i*i是否等于x；
                ans++;
            }
        } 
    }
    return ans;
}
int main(){
    cin>>n;
    int m=js(n);
    cout<<m;
    return 0;
}

接下来是第二种方法，STL大法！(Standard Template Library,标准模板库) 鉴于STL不是重点，了解会用就好，可以当成一个不错的工具。

这里我们用到的是set容器，内部实现为“红黑树”，是一个不重复的有序集合。

#include<bits/stdc++.h>
using namespace std;
int x;
set<int>t; //声明一个int类型的set数组t；
int js(int m){
	int ans=0;
	for(int i=1;i<=sqrt(m);i++){
		if(m%i==0){
			t.insert(i);
			t.insert(m/i); //读入因数
		}
	}
	return t.size();  //返回因数个数
}
int main(){
	cin>>x;
	cout<<js(x);
	return 0;
}

好了，这就是如何快速的求一个正整数的所有因数的个数的方法。

当然，如果数据本身不是很大的话，可以用一下另一种方法，平常可以自己计算一下。

其实求一个数的因数的个数是有规律的：
设N分解质因数之后的结果是：N=p^a * q^b * r^c
则N的因数的个数是：（a+1）*（b+1）*（c+1）个。
即有每个质因数的指数加1的乘积个。首先我们需要构造一个质数表，可以采用欧拉筛。

方法如下：

//欧拉筛
#include <bits/stdc++.h>
using namespace std;
long long m,i,j,cnt=0;
bool vis[10000001];
int p[10000001];
void is_sh(long long n){
   for(i=2;i<=n;i++){
   	if(!vis[i]) p[++cnt]=i;
   	for(j=1;j<=cnt&&p[j]*i<=n;j++){//开始筛，注意条件
   		vis[p[j]*i]=true;
   		if(!i%p[j]) break;
	   }
   }
}
int main(){
	cin>>m;
    is_sh(100001);//在10的5次方范围内筛素数
    for(int i=1;i<=m;i++){//（在上述范围内）按照从小到大的顺序输出m个质数 
    	cout<<p[i]<<" ";
	}
    return 0;
}

然后开始：

//欧拉筛
#include <bits/stdc++.h>
using namespace std;
int a,m,i,j,cnt=0;
bool vis[10000001];
int p[10000001];
int b[100000];
void is_sh(int n){
   for(i=2;i<=n;i++){
   	if(!vis[i]) p[++cnt]=i;
   	for(j=1;j<=cnt&&p[j]*i<=n;j++){
   		vis[p[j]*i]=true;
   		if(!i%p[j]) break;
	   }
   }
}
int js(int x){
	int ans=0;
	int k=x;
	int l=1;
	while(k!=1){
		if(k%p[l]==0){
			b[l]++; //质因数的个数
			k/=p[l]; 
		}else{
			
			l++;
		}
	}
	ans=b[1]+1; //开始计算
	for(int i=2;i<=l;i++){
		ans*=(b[i]+1);
	}
	cout<< ans;
}
int main(){
	cin>>a;
    is_sh(100001);//在10的5次方范围内筛素数
    js(a);
    return 0;
}

但是如果我们这样写的话，可能会有些慢。我们应该牢记“多一点想，少一点算”的指导方针。

我们可以很容易的知道，1到n的因子个数，可以看成共含有2因子的数的个数+含有3因子的数的个数……+含有n因子的数的个数，同时在1~n中含有“2”这个因子的数有n/2个，3有n/3个，以此类推，就出来结论了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,s;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		s+=n/i;
	}
	cout<<s<<endl;
}

就是这么多了。如果有什么不解或者建议，请在评论区留言，感谢。

文章来源地址https://www.toymoban.com/news/detail-664225.html

到了这里，关于C++，如何快速的求一个正整数的所有因数的个数？的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！