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/

相关文章:

python - RSA,从列表中计算值(value)

c++ - 如何在 Sieve_of_Eratosthenes 中使用更少的内存

java - 跨项目共享 JBoss/WildFly 安全域

java - 在 Android 1.6 上使用 Google Guava

algorithm - 布伦特周期检测算法

java - 使用筛子查找小于 LONG 数的素数

java - SPOJ 上的 PrimeNumber 生成器运行时错误

java - 我可以使用 Soot 来查找给定起始类或方法的潜在执行路径和资源使用情况吗?

JavaFX 动画折线图

java - 在 Java 中对 ArrayList<List> 进行排序