6

My question is related to the following code:

public static void main(String[] args) {

    // Find Prime Numbers from 0 to 100
    int i;
    for (i=2; i <= 100; i++) {
        int j = 2;
        boolean iPrime = true;

        //The following line gives incorrect results, but should execute faster
        //  while ((iPrime = true) && (j < (i / 2 + 1))) {
        //The following line gives correct results but performs un-necessary operations
        //by continuing to calculate after the number is found to be "not prime"
        while (j < (i / 2 + 1)) {

            j++;
            if ((i % j) == 0) {
                iPrime = false;
                //System.out.println(j + " is a factor of " + i);
            }
        }
        if (iPrime) {
            System.out.println(i + " is a prime number!");
        }
    }
}

Now, as I've commented in the code, what I'm trying to achieve is a faster execution of my program by executing the 'while' loop only when iPrime = true. 50% of numbers are divisible by 2 and so this once this has been established the calculations can stop.

I'm doing this project as part of a beginners 'example' from a book, I actually am trying to calculate up to 1000000 as quickly as possible just for my own "extra credit"...

I read that the "short circuit 'and' operator" && only evaluates the second half of the statement if the first half is true, if it is false, the two are not evaluated against each other (saving CPU)

And it will also exit the loop, which will save even more CPU...

But for some reason, it is not working correctly! I've put more System.out.println() statements throughout, listing what 'iPrime' is - and the output is stranget... It switches iPrime on and off and evaluates every number, which I cannot understand.

4

4 回答 4

7

if((iPrime = true) && ...)应该是if((iPrime) && ...)。

通过这样做isPrime = true，您将 true 分配给isPrime而不是将其值与true.

您可能还希望看到这个以更好地理解代码中发生的情况：

在运行时，赋值表达式的结果是赋值发生后变量的值。赋值表达式的结果本身不是变量。

因此，当您使用=运算符而不是==（当您将某些内容与true- 而不是写if(someBoolean == true)您只是 write时删除if(someBoolean)）时，您实际上总是满足条件！

于 2013-04-20T13:56:09.803 回答
4

简单地=变成==，即改变

while ((iPrime = true) && (j < (i / 2 + 1)))

进入

while ((iPrime == true) && (j < (i / 2 + 1)))

具有更好性能的完整代码

public static void main(String[] args) {
    // Find Prime Numbers from 0 to 100
    System.out.println(2 + " is a prime number!");
    for (int i = 3; i <= 100; i += 2) {
        boolean isPrime = true;
        for (int j = 3; j * j <= i; j += 2) {
            if ((i % j) == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            System.out.println(i + " is a prime number!");
        }
    }
}

我能想到的最快的方法是Sieve of Eratosthenes。

于 2013-04-20T13:54:34.813 回答
1

首先在运行您的代码时，我发现它显示 4 作为质数，这是不正确的。原因是您的 j++ 行的位置。您应该将 while 循环更改为：

while (j < (i / 2 + 1)) {   
                if ((i % j) == 0) {
                    iPrime = false;

                    //System.out.println(j + " is a factor of " + i);
                    break;
                }
                j++;
            }

继续第二部分，当您确定该数字不是素数时，您希望避免额外的计算。您可以在上面的代码中为此使用 break 语句。

注释部分不起作用，因为您有分配而不是相等比较。

于 2013-04-20T14:02:06.337 回答
1

johnchen902 / Maroun Maroun 修复了你的错误；此外，您可以执行的优化是

System.out.println("2 is a prime number!"); // the for loop won't detect 2 anymore
for (i=3; i <= 100; i+=2) {

此外，您可以对具有所有前面的素数的数字执行模运算符以查看它是否为素数，而不是对具有所有前面奇数的数字执行模运算符以查看它是否为素数 - 例如，将找到的素数存储在 ArrayList 中，并在素数测试中遍历该列表。

对于 CPU 效率非常高（但空间效率较低）的算法，请使用埃拉托色尼筛

于 2013-04-20T14:00:21.637 回答