快速添加数千个数字的有效方法是什么？

Question

我正在尝试解决一个挑战，但遇到了障碍。我是一名初级程序员，试图添加数万个数字。如果我等待的时间足够长，我的程序可以很容易地得出正确的总和，但是，我正在寻找一种更有效的方法。

快速添加数千个数字的有效方法是什么？

旁注：我一直在阅读有关模块化算法的内容，但我无法完全理解它。不确定这对这种情况是否有用。

我正在尝试获取小于 2 000 000 的每个素数的总和。到目前为止，这是我的代码：

public class Problem10 {
    public static void main (String[] args) {
        long sum = 0L;

        for(long i = 1L; i < 2000000; i++) {
            if(isPrimeNumber((int)i)) {
                sum += i;
            }
        }
        System.out.println(sum);
    }

    public static boolean isPrimeNumber(int i) {
        int factors = 0;
        int j = 1;

        while (j <= i) {
            if (i % j == 0) {
                factors++;
            }
            j++;
        }
        return (factors == 2);
    }
}

Answer 1

这看起来像是家庭作业，所以我不会在代码中为您提供解决方案。您至少可以自己编写代码。

---

在您的代码中，isPrimeNumber() 占用了大部分时间——如果我不得不猜测的话，我会说占了 90-99%。你可以做些什么来让它更快是实施 Sieve of Eratosthenes.

首先，您创建一个包含所有质数的数组¹。您应该从一个值开始：2。要查找更多素数，请遍历从 3 到您想要的最大数字的每个整数。对于这些数字中的每一个，检查该数字是否可以被数组中的任何素数整除。如果你数组中的下一个质数大于 i / 2，你就知道 i 是质数，你可以将它添加到你的数组中。

找到从 1 到 n 的所有质数后，求和的唯一方法是遍历数组。那部分无法优化，但反正不会花很长时间。

¹ 有两种方法可以做到这一点。一种是只使用 ArrayList 或 LinkedList，并根据需要添加数字。另一种是创建一个与您需要的一样大或更大的数组。如前所述here，等于或小于n的素数个数小于(n / log(n)) * (1 + 1.2762 / log(n))，只要n大于598即可。如果n小于598，可以直接创建一个数组长度 109.

---

关于标题中的问题，"What is an efficient method for adding thousands of numbers quickly?"，我唯一能想到的就是多线程。创建一个包含所有要求和的数字的数组，然后让许多线程对数组的不同部分求和。之后，对每个线程的所有结果求和。这种方法可能只会在对大量数字求和时明显更快，例如数十万或数百万。

Answer 2

您可以用此替换您的 isPrimeNumber() 方法以大大加快速度。

public static boolean isPrimeNumber(int i) {
    if (i==2) return true;
    if (i==3) return true;
    if (i%2==0) return false;
    if (i%3==0) return false;

    int j = 5;
    int k = 2;

    while (j * j <= i) {
        if (i % j == 0) return false;
        j += k ;
        k = 6 - k;

    }
    return true;
}