我试图在 Java 中找到低于 200 万的素数总和 [英] I'm trying to find the sum of primes below 2 million in Java

问题描述

我试图找到数百万以下的素数之和.当我试图找到低于十万的素数总和时，我的代码有效，但是当我找到大数时，它不起作用.所以我需要一些帮助才能让这项工作适用于大数字......

I'm trying to find the sum of primes below millions. My code works when I try to find the sum of primes below hundred thousands but when I go large numbers it doesn't work. So I need some help to get this work for big numbers...

import java.util.Scanner;
public class sumPrime {

  public static void main (String args []){

    long n = 2000000; int i; int j;int sum =0;
    for (i=2; i <n; i++){
        for (j=2; j<i; j++){
            if (i%j==0){
                break;
            }
        }
        if (i==j){
            sum +=i;
        }
    }
    System.out.print(sum);
  }
}

推荐答案

1. 可以通过提前停止内部循环来改进您的代码.如果一个数 N 不是质数，那么它必须至少有一个因子(除了 1)小于或等于 sqrt(N).在这种情况下，这个简单的更改应该会使程序快 1000 倍左右.

1. Your code could be improved by making the inner loop stop earlier. If a number N is not prime, then it must have at least one factor (apart from 1) that is less or equal to sqrt(N). In this case, this simple change should make the program roughly 1000 times faster.

要了解简单且(更)高效的算法，请阅读 埃拉托色尼筛法.

For a simple and (more) efficient algorithm, read up on the Sieve of Eratosthenes.

Bug - 您的 sum 必须是 long.int 可能会溢出.

Bug - your sum needs to be a long. An int will probably overflow.

请注意，Eratosthenes 筛法的经典公式需要大量布尔值(或位图)，其大小取决于您感兴趣的最大素数候选者.在这种情况下，这意味着一个 2Mbyte 的数组(或者更小，如果您使用位图)......这太小了，不用担心.此外，您可以通过分阶段筛选来减少内存使用量，但这会使代码更加复杂.

Note that the classic formulation of Sieve of Eratosthenes needs a large array of booleans (or a bitmap) whose size depends on the largest prime candidate you are interested in. In this case that means a 2Mbyte array (or smaller if you use a bitmap) ... which is too small to worry about. Also, you can reduce the memory usage by sieving in stages, though it makes the code more complicated.

这篇关于我试图在 Java 中找到低于 200 万的素数总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！