作业帮 > 综合 > 作业

求判断一个正整数是不是素数的高效算法 不是那种从 2一直除到n/2的那种算法 要时间复杂度低的

来源:学生作业帮 编辑:拍题作业网作业帮 分类:综合作业 时间:2024/05/08 06:18:45
求判断一个正整数是不是素数的高效算法 不是那种从 2一直除到n/2的那种算法 要时间复杂度低的
O(Sqrt[n])的一般情况都可以了,最高效的应该是Miller-Rabbin素数测试法,稍有点复杂.具体的做法网上都有.