绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
如何快速求出与n互素的数有多少个?
2022-09-07 17:18:43

小K



1
故事起源
一个数n,在小于等于n的正整数[1,n]中,与n互素的数有多少个呢?
(注:x与n互素,说明x与n的大公约数为1)



02
分析
直观的方法当然就是直接枚举所有小于n的数,再通过求大公约数判断即可。
但当n很大的时候,这个方法就不优了。可能有同学已经发现了,这个不就是欧拉函数的定义吗,所以今天我们从数学上来分析如何快速求解。


03
欧拉函数
欧拉函数定义如下:


欧拉函数具有几个的性质,先介绍几个常用的数学符号,便于描述。


3.1
性质1

当n为素数时,很明显phi(n)=n-1,因为所有小于n的数都与n互素。


当n为某个素数p的幂次时,即n=p^k,则与n不互素的一定为p的倍数。

[1,n]中p的倍数一共有p^(k-1)个,所以互素的即为总数减去不互素的个数。


3.2
性质2

欧拉函数是一个积性函数,当整数m,n互素时,phi(mn)=phi(m)*phi(n)。


这个性质的证明需要用到同余和集合相关的定理,有点复杂,以后写同余相关的知识再专门分享如何证明,现在就先记住这个性质就行了。


04
计算
有了这2个性质就可以推导出欧拉乘积公式。


接下来就只需要考虑如何对n进行质因素分解。

简单的方式可以直接枚举,先找到小的质因子p1,然后除去所有p1因子,再对剩余的数继续分解。



05
代码实现
int euler_phi(int n) {
    int m = sqrt(n + 0.5);
    int ans = n;
    for (int i = 2; i <= m; ++i) {
        if (n == 1break;
        if (n % i == ) {
            ans = ans / i * (i - 1);
            while (n % i == ) n /= i;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}


06
总结
现在的算法复杂度主要取决于寻找个质因子,枚举并不是快的方法,更快的方法是基于费马小定理,miller_rabin,pollard_rho等原理的随机化算法。

数论是一个大类,在很多地方都有重要的应用,而素数在密码学中应用也很广泛,今天分享的算是数论入门的一个介绍,后面还会分享更多有关数论的知识。


分享好友

分享这个小栈给你的朋友们,一起进步吧。

算法交易的佳编程语言是什么?
创建时间:2022-04-27 16:03:53
编程语言的运用,必须考虑战略参数、性能、模块化、开发、弹性和成本等多种因素。 一旦要执行某个交易策略,就要构建整个算法交易系统。这包括硬件选择、操作系统和系统对罕见的、潜在的灾难性事件的弹性。 算法交易系统是一个综合性结构,能够考虑到的因素包括:研究工具、投资组合优化器、风险管理器、执行引擎、交易策略设计、交易频率及交易量等。 在决定编写自动交易系统的“佳”语言之前,必须要先定义系统要求。比如,系统是否纯粹用于执行?系统是否需要风险管理或投资组合构建模块?系统是否需要高性能的回测器? 对于大多数策略,交易系统可以分为两类:研究和信号生成。 1.研究 根据历史数据评估战略绩效。根据先前的市场数据评估交易策略的过程称为回测。数据大小和算法复杂度将对回测器的计算强度产生很大影响。CPU速度和并发性通常是优化研究执行速度的限制因素。 2.信号生成 从算法生成一组交易信号并将此类订单发送到市场,通常通过经纪公司。对于某些策略,需要高水平的性能。网络带宽和延迟等 I/O 问题通常是优化执行系统的限制因素。则整个系统的每个组件的语言选择可能会大不相同。 非凸科技研发的算法策略在交易成功率和交易速度等核心指标上表现优异,目前正基于Rust生态打造高效率、低延迟、高可靠、全内存高频交易平台,满足客户在风控、交易、数据、系统等方面的交易需求。 如果你想追求高效和,可以尝试下Rust~
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 非凸科技
    栈主
戳我,来吐槽~