2

我正在尝试运行此代码来打印小于 200 万的所有质数的总和。这个循环永无止境。谁能告诉我代码有什么问题？不过，它似乎适用于较小的数字。

public static void main(String[] args) {

        long result = 1;

        for(int i=0; i<2000000; i++) {
            if(isPrime(i)) {
                result+= i;
            }
        }
        System.out.println(result);

    }
private static boolean isPrime(long n) {
    boolean result = false;

    for(long i=2; i<(long)Math.sqrt(n); i++) {
        if(n%i == 0) {
            result = false;
            break;
        }
        else result = true;
    }
    return result;
}
4

5 回答 5

5

在isPrime你只测试除以 2：

private static boolean isPrime(long n) {
    boolean result = false;

    for(long i=1; i<n/2; i++) {
        if(n%2 == 0) {
            result = false;
            break;
        }
        else result = true;
    }
    return result;

}

它应该除以每个i并从 2 开始：

for(long i=2; i<n/2; i++) {
    if(n%i == 0) {
      ...

实际上，在您当前的版本中，奇数n将继续除以 2，n/2而不是更快地停止。考虑 n = 21。您从 1 到 10 除以 2，而不是在第 3 步除以 3 并退出。

它不仅给出了错误的结果，而且需要比需要更长的时间才能得出一个return声明。

编辑：为了获得更快的结果，请查看 Erathostenes 方法的筛子：

public static long sumOfPrimes(int n) {

    long sum = 0;

    boolean[] sieve = new boolean[n];
    for(int i = 2; i < Math.sqrt(n); i++) {
        if(!sieve[i]) {
            for(int j = i * i; j < n; j += i) {
                sieve[j] = true;
            }
        }
    }

    for(int i = 2; i < n; i++) {
        if(!sieve[i]) {             
            sum += i;
        }
    }

    return sum;
}

编辑#2：发现新版本的一些错误。这是更正后的：

private static boolean isPrime(long n) {
    boolean result = false;

    if(n == 2 || n == 3) return true;

    for (long i = 2; i <= (long) Math.sqrt(n); i++) {
        if (n % i == 0) {
            result = false;
            break;
        } else
            result = true;
    }

    System.out.println(n + " " + result);
    return result;
}
于 2012-06-04T11:48:33.203 回答
2

你有一个错误isPrime()

测试应该是：

if(n%i == 0) { ...

并且您需要从 开始计数2，而不是1，因为每个数字除以 时都有余数为零1！

此外，无需过去Math.sqrt(n)。

你应该把它改成这样：

private static boolean isPrime(long n) {
    long max = (long)Math.sqrt(n);
    for (long i = 2; i < max; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

仅供参考，通过此更改，我在 PC 上测试了该程序，并在 1 秒内完成，结果为143064094810

于 2012-06-04T11:48:36.660 回答
0

一个简单的函数必须在每次运行时计算直到（或至少到）isPrime的所有素数。确保你的 isPrime 函数缓存了它的结果！isqrt(i)

于 2012-06-04T11:46:54.547 回答
0

经过测试且无错误的 Prime 检查功能

static boolean isPrime(int n) {
    if (n == 1) return false;

    for(int i = 2; i <= n/2; i++)
        if(n % i == 0)
            return false;

    return true;
}
于 2013-08-28T06:59:52.120 回答
0

这是一个使用JOptionPane的Prime的完整程序，即Java GUI

import javax.swing.*;

public class ChkPrime {
    public static void main(String[] args) throws NumberFormatException {
        String str = JOptionPane.showInputDialog(null, "Enter any number: ","Input...", 3);

        try {
            int num = Integer.parseInt(str);


            if (num == 1)
                JOptionPane.showMessageDialog(null, "Your inputed no. " + num + " is not prime.","Error!", 0);

            for(int i = 2; i <= Math.sqrt(num); i++) {
                if(num % i == 0) {
                    JOptionPane.showMessageDialog(null, "Your inputed no. " + num + " is not prime.","Error!", 0);
                    System.exit(0);
                }
            }

            JOptionPane.showMessageDialog(null, "Your inputed no. " + num + " is prime.","Yeh! Got it!", 1);
        }

        catch (NumberFormatException e) {
            JOptionPane.showMessageDialog(null, "Please input numbers...","Error!", 0);
            main(null);
        }
    }
}
于 2014-01-19T13:17:14.747 回答