ACM数论 梅森素数检测问题如果数M(p) = 2^p - 1,且p和M(p)都是素数,我们称M是梅森素数.现给出一个整数p(1
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/28 20:07:27
![ACM数论 梅森素数检测问题如果数M(p) = 2^p - 1,且p和M(p)都是素数,我们称M是梅森素数.现给出一个整数p(1](/uploads/image/z/10372293-45-3.jpg?t=ACM%E6%95%B0%E8%AE%BA+%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0%E6%A3%80%E6%B5%8B%E9%97%AE%E9%A2%98%E5%A6%82%E6%9E%9C%E6%95%B0M%28p%29+%3D+2%5Ep+-+1%2C%E4%B8%94p%E5%92%8CM%28p%29%E9%83%BD%E6%98%AF%E7%B4%A0%E6%95%B0%2C%E6%88%91%E4%BB%AC%E7%A7%B0M%E6%98%AF%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0.%E7%8E%B0%E7%BB%99%E5%87%BA%E4%B8%80%E4%B8%AA%E6%95%B4%E6%95%B0p%EF%BC%881)
ACM数论 梅森素数检测问题如果数M(p) = 2^p - 1,且p和M(p)都是素数,我们称M是梅森素数.现给出一个整数p(1
ACM数论 梅森素数检测问题
如果数M(p) = 2^p - 1,且p和M(p)都是素数,我们称M是梅森素数.
现给出一个整数p(1
ACM数论 梅森素数检测问题如果数M(p) = 2^p - 1,且p和M(p)都是素数,我们称M是梅森素数.现给出一个整数p(1
刚在wiki上看到梅森素数的这个判断性质:
Mn为素数当且仅当Mn整除Sn-2(S0=4,S(k) = S(k − 1)^2 − 2,k > 0).
用这个将使得复杂度由O(n)降到O(logn)
参考资料:
http://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0