约数的个数定理
本文最后更新于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;
}
如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇