【摘要】 为了快速实现素数测试,基于容斥原理给出了一种试除小素数优化策略,然后将该优化策略与Leh-m ann算法以及基于递归技术改进的计算余数算法相结合,提出了一种实现快速素数测试的Monte Carlo概率算法.利用该算法并结合C++6.0具有的特殊整型-int64特性,可以快速测定大奇数(至少78位十进制数)是否为素数.更多还原

【Abstract】 For the efficient testing of prime number,a try-division optimization strategy is provided based on inclusion-exclusion principle.Combined the optimization strategy and Lehmann algorithm with the algorithm of remainder calculation improved by recursion techniques,a Monte Carlo probabilistic algorithm is proposed to implement rapid primality test.Using the new algorithm and the typical integer type-int64 characteristic of C++6.0,the testing of prime number(at least 78 digital) can be implemented quickly.更多还原