首页 > 代码库 > 分解质因数的技巧
分解质因数的技巧
背景:
有时分解一个很大的合数,因为可能质因子很大,导致分解时复杂度不是严格O(log2n),需要用一点技巧使其复杂度得到保证。
做法:
在筛法求质数时,不用把质数存储成一张表,而用一个数组big[i]保存每个数(不管是质数还是合数)的最大质因数,接着在分解一个数x时,令y=x,之后不断地y/=big[y],并且把每次的big[y]作为x的一个质因数,这样就可以了。
20161115
分解质因数的技巧
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。