本文最后更新于558 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com
这个定理百度百科里面是这么解释的:
定理简证
实现代码
int solv(int x)
{
int i = 2, cnt = 0, ans = 1;
do
{
cnt = 0;
while (x%i==0)
{
cnt++;
x /= i;
}
ans *= (cnt + 1);
i++;
} while (x!=1);
return ans;
}
这是一种比较简单的实现方法,但时间复杂度比较大接近O(x),可以通过预处理出素数,接着只需要遍历一遍小于x的素数即可。
优化代码
#include <iostream>
using namespace std;
int prime[20000];//素数,需要进行预处理
bool isnp[200000];//不是素数
void init(int n)//线性筛,预处理出素数
{
int cnt = 0;
for (int i = 2; i <= n; i++)
{
if (!isnp[i])
prime[cnt++] = i;
for (int j=0;j<cnt;j++)
{
if (prime[j] * i > n)
break;
isnp[prime[j] * i] = 1;
if (i % prime[j] == 0)
break;
}
}
}
int solv(int x)//求约数的个数
{
int i = 0, cnt = 0, ans = 1;
do
{
cnt = 0;
while (x % prime[i] == 0)
{
cnt++;
x /= prime[i];
}
ans *= (cnt + 1);
i++;
} while (x != 1);
return ans;
}
int main()
{
init(200000);
cout << solv(20200);
return 0;
}