java - 素数计算器需要太多时间(JAVA)

标签 java primes

当我运行此代码来查找低于 20 的素数总和时,它工作得很好,但是当尝试查找低于 2500000 的总和时,它会花费太多时间。至少已经过去 20 分钟了,它仍在运行。看起来好像不起作用。我该如何修复它?

class PrimeSummation {
    public static void main(String[] args) {
        int sum = 0;
        for(int i = 1; i < 2500000; i++) {
            int count = 0;
            for(int j = 1; j < i + 1; j++) {
                if((i%j) == 0) {
                    count++;
                }
            }
            if(count == 2) {
                sum += i;
            }
        }
        System.out.println(sum);
    }
}

最佳答案

sum不能是int因为答案是219697708195Integer.MAX_VALUE只有2147483647 。您必须使用longBigInteger相反。

你的算法非常慢,因为对于2500000中的每一个你从头开始决定它是否是素数,而你测试一个数是否是素数的方法(尝试每一个可能的因素)并不是很有效。

以下代码在我的机器上大约十分之一秒内生成答案。

int num = 2500000;
long sum = 0;
boolean[] arr = new boolean[num];
for (int p = 2; p < num; p++) {
    if (!arr[p]) {
        sum += p;
        for (int k = p * 2; k < num; k += p)
            arr[k] = true;
    }
}
System.out.println(sum);

关于java - 素数计算器需要太多时间(JAVA),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32417266/

相关文章:

java - JLabel - 将较长的文本显示为多行?

java - 线程中出现异常,java代码将无法正常执行。 if/else 语句

java - 清除Java中位集中索引的所有倍数?

java - 为什么这个主要检查器可以工作,但如果我试图提高它的效率却不起作用

java - 识别文本文件中的重复数字

java - 使用 Java Streams 从嵌套映射中提取列表

java - 自动将类添加到源代码管理

java - 数的原数

f# - 此质因数分解代码适用于小数,但对于大数会因 OutOfMemoryException 而失败?

multithreading - Erlang 和进程