在Java中寻找素数
我遇到了一个Java程序,它可以发现给定的数字是否是素数。 这是代码
class FindPrime {
public static void main(String args[]) {
int num;
boolean isPrime;
num = 14;
if (num < 2)
isPrime = false;
else
isPrime = true;
for (int i = 2; i <= num / i; i++) {
if ((num % i) == 0) {
isPrime = false;
break;
}
}
if (isPrime)
System.out.println("Prime");
else
System.out.println("Not Prime");
}
}
在这里,我不知道为什么我<;=num/i用于for循环。谁能给我解释一下吗
# 1 楼答案
i <= num/i
就像做i <= sqrt(num)
如果num不是素数,我们可以把它分解成
num = a * b
如果num的一个因子大于num的平方根,那么另一个必须小于num的平方根。
如果两者都大于它,那么它的乘积将大于num
# 2 楼答案
在程序中添加for循环是不明智的,因为它们会给u带来更大的时间复杂度O(n)线性时间复杂度,但是if语句在这里是一个例子
# 3 楼答案
这是检查素数与否的更好方法
# 4 楼答案
下面的解决方案使用Sieve of Sundaram打印出用户提供的所有素数:
请注意,对于较大的输入,可能会出现OutOfMemory错误
# 5 楼答案
限制条件是性能优化:
例如
num = 11
和i = 3
,到目前为止,我们已经检查了11是否可以被2除(否),现在正在移动到3,我们应该检查它,答案是不,它不能被3除。现在我们移动到4,我们是否应该检查11是否可以除以它?这样的除法将产生2.75,这个值小于我们已经检查过的3。任何更高的i
将产生更小的值,我们已经检查过所有这些值,因此进一步检查没有意义。我们现在知道答案了# 6 楼答案
不要忘记,对于类循环
for(A;B;C)
表达式A在循环开始时计算一次,表达式B从第一个循环开始计算每个循环,表达式C从第二个循环开始计算因此,最好将偏差从B部分移动到A部分
我<;num/i是性能优化,而且检查第一个
Math.sqrt(num)
元素就足够了