编写Kotlin函数isPrimeNumber
编写Kotlin函数isPrimeNumber
提问于 2021-03-14 12:05:02
练习：编写一个素数测试isPrime(num: Int)，用于整数m >= 2检查该整数是否为素数。
My解决方案：
fun main(args: Array) {
var isPrime: Boolean = false
for (i in 2..101) {
isPrime = isPrime(i)
if (isPrime) {
println("$i => ${isPrime(i)}")
}
}
}
fun isPrime(num: Int): Boolean {
val upperLimit = num / 2;
var i = 2
while (i <= upperLimit) {
if (num % i == 0) {
return false
}
i++
}
return true
}Could我的解决方案在效率方面有所改进？
回答 1
Code Review用户
回答已采纳
发布于 2021-03-14 12:33:14
两个简单的改进
检查到n的平方根，而不是n/2。所以对于101，你只需要检查n到10，而不是50。如果你的数字不是素数，那么它的因子之一必须小于等于它的平方根。
不要检查2的倍数，所以做一个测试，看看这个数字是否可以除以2，然后只测试从3开始的奇数。
因此，如果你测试101的祭司，这些变化意味着，而不是2.50的分裂测试，你只测试2,3,5,7,9
其他需要考虑的事情
使用平方根n下面的素数。所以，如果你知道2,3,5,7是唯一在101平方根以下的素数，你只需要测试这些数字的整除性，就可以显示101是素数。
一个更复杂的解决方案将是查看米勒拉宾测试的确定性版本，如描述的这里，如果您只想知道某个特定值是否为素数，那么这个方法很好。
如果您希望n以下的所有素数都是素数筛，那么最有效的方法就是
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/257141
复制相关文章
相似问题
腾讯云开发者
