Ruby 代码如下
1 | def isZhishu?(num) |
上面这个方法非常笨重,时间复杂度是 O(n^2),可以进行一些优化。根据@sdpfoue 的建议,做了优化。
首先就是可以只对大于3的奇数进行检查,因为偶数肯定可以被2整除,所以不需要考虑。
另外循环相除的时候,可以只除以质数,这样也能够减少不少步骤。但是会增加空间的消耗,就是所谓的用空间换时间。
Ruby 代码如下
1 | def isZhishu?(num) |
上面这个方法非常笨重,时间复杂度是 O(n^2),可以进行一些优化。根据@sdpfoue 的建议,做了优化。
首先就是可以只对大于3的奇数进行检查,因为偶数肯定可以被2整除,所以不需要考虑。
另外循环相除的时候,可以只除以质数,这样也能够减少不少步骤。但是会增加空间的消耗,就是所谓的用空间换时间。