[首页]
[文章]
[教程]
首页
Web开发
Windows开发
编程语言
数据库技术
移动平台
系统服务
微信
设计
布布扣
其他
数据分析
首页
>
其他
> 详细
约数大合集(超详细!!!)
时间:
2019-08-22 00:05:25
阅读:
117
评论:
0
收藏:
0
[点我收藏+]
整数惟一分解定理的推论
1、求N的正约数集合
因为约数总是成对出现的(除了完全平方数)。因此只需扫描1~sqrt(N)之间的数就能得到N的正约数集合。
2、求1~N的每个数的正约数集合
3、约数个数
算术基本定理中,根据拆分后的素因子的指数,我们可以求出每个 N 的约数的个数。
根据这个式子,我们可以用
线性筛
去筛出当前 1~N 的约数个数。筛的过程中,我们需要保存下
最小素因子的个数
。
下面推导中
d(i)
表示 i 的约数个数
num[i]
表示 i 的最小素因子的个数
prim[i]
表示 第 i 个素数
①
当前数N是素数
这种情况我们很容易得到,当前的
d(N) = (1+1) = 2
, 因为素数只有一个素因子(就是它本身),并且指数为 1 。 而最小素因子个数
num[N] = 1
②
i%prim[j] !=0
这种情况,i 当中,并不包含 prim[j] 这个素因子,然而,i*prim[j] 中, 包含了一个 prim[j]我们可以从前面得到 i 的所有约数个数 然后在补上 当前多了 素因子 prim[j] 的个数所以最后
d(i*prim[j]) = d(i)*d(prim[j])
而且由于 当前的 prim[j] 必然是 i*prim[j] 的最小素因子 (因为从小到大枚举啊!), 我们要记录下这个最小素因子的个数所以保存一个个数
num[i*prim[j]] = 1
③
i%prim[j]==0
这种情况, i 中必然包含了至少 1 个 prim[j] ,而且 prim[j] 也必定是 i 的最小素因子,因为每次枚举都是从小的素数开始枚举。
而 i*prim[j] 比起 i 则是多了一个最小素因子个数,即 1+a1
那么 i*prim[j] 的约数个数 应该是 (1+a1+1)(1+a2)…(1+an)
之后,我们就要用到我们之前记录下的最小素因子个数了,因为我们可以知道 i 的最小素因子个数 为 num[i] ,而 d(i) 中 已经包含了(1+a1)(1+a2)…(1+an) 这时我们 我们可以除去第一项1+a1 然后乘以 1+a1+1 ,就可以得到 d(i*prim[j]) 的约数个数了。
d(i*prim[j]) = d(i) / (num[i]+1) * (num[i]+2)
当前
num[i*prim[j]] = num[i]+1
,继续保存下当前最小素因子个数。
↓↓↓用线性筛打表出 1 到 N 的数的约数个数。
4、约数和
算数基本定理中,如果要求N的约数的和,可以用这条式子。
同样,我们一样可以用这条式子去筛出当前 N 的约数和。 筛的过程中,我们需要保存最小素因子的那一项的和,即
下面推导中
sd(i)
表示 i 的约数和
sp[i]
表示 i 的最小素因子的等比数列的和 (上面说要保存的那一项)
prim[i]
表示第 i 个素数
①
当前数N是素数
这种情况我们可以很容易得到,当前的
sd(N) = 1+i
因为素数只有一个素因子,即只有一项合式,且指数最高为 1 。
而该项
sp[N] = 1+i
②
i%prim[j] !=0
这种情况,i 当中,并不包含 prim[j] 这个素因子,然而,i*prim[j] 中, 包含了一个 prim[j]而前面我们已经得到了 i 的约数和了,而其中不包括 (1+prim[j]) 这一项,而 i*prim[j] 的约数和只是多了这一项。
i 的约数和是
那么 i*prim[j] 的最后结果应该是
即
sd(i*prim[j]) = sd(i) * sd(prim[j])
而 prim[j] 是 i*prim[j] 的最小素因子 (因为从小到大枚举),因此
sp[i*prim[j]] = 1+prim[j]
③
i%prim[j]==0
这种情况, i 中必然包含了至少 1 个 prim[j] ,而且 prim[j] 也必定是 i 的最小素因子,因为每次枚举都是从小的素数开始枚举。
只不过 i*prim[j] 比起 i 则是在最小素因子那一项多了
那么 i*prim[j] 的约数和就是
之后,我们用到前面保存下来的最小素因子那一项的和,因为 i 中 应该是
我们可以知道最小素因子的那一项的和,而要得到
只需要将第一项 乘以 prim[j] 然后再 加一,就可以得到了。
sd(i*prim[j]) = sd(i) / sp[i] * (sp[i]*prim[j]+1)
当前
sp[i*prim[j]] = sp[i]*prim[j]+1
,继续保存最小素因子一项的和。
用线性筛打表出 1 到 N 的约数和。
约数大合集(超详细!!!)
原文:https://www.cnblogs.com/ljy-endl/p/11391853.html
踩
(
0
)
赞
(
0
)
举报
评论
一句话评论(
0
)
登录后才能评论!
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
2021/09/28 scripts
2022-05-27
vue自定义全局指令v-emoji限制input输入表情和特殊字符
2022-05-27
9.26学习总结
2022-05-27
vim操作
2022-05-27
深入理解计算机基础 第三章
2022-05-27
C++ string 作为形参与引用传递(转)
2022-05-27
python 加解密
2022-05-27
JavaScript-对象数组里根据id获取name,对象可能有children属性
2022-05-27
SQL语句——保持现有内容在后面增加内容
2022-05-27
virsh命令文档
2022-05-27
教程昨日排行
更多>
1.
list.reverse()
2.
Django Admin 管理工具
3.
AppML 案例模型
4.
HTML 标签列表(功能排序)
5.
HTML 颜色名
6.
HTML 语言代码
7.
jQuery 事件
8.
jEasyUI 创建分割按钮
9.
jEasyUI 创建复杂布局
10.
jEasyUI 创建简单窗口
友情链接
汇智网
PHP教程
插件网
关于我们
-
联系我们
-
留言反馈
- 联系我们:wmxa8@hotmail.com
© 2014
bubuko.com
版权所有
打开技术之扣,分享程序人生!