2

For Project Euler problem #10, I wrote a program to find the sum of all prime numbers between 2 and 2,000,000.

My code works for smaller values like 50 or 100, but when I try it with 2,000,000 it returns a value that is too small by 141,675.

I thought it might be because the answer was too long to fit in a long, which is why I use BigInteger, but I've since learned that's not a factor. I appreciate any thoughts.

public class ProblemTen {


/**
 * Precondition:  all the bits in the set are set to true
 * This method uses the Sieve of Eratosthenes
 * @param p the starting prime number
 * @param b the BitSet array
 * @param s the length of the original BitSet array
 * @return BitSet with all the prime indexes set to true
 */
public static BitSet findPrimes(int p, BitSet b, int s) {
    //System.out.println(b);
    while (p*p < s) {  // repeat until p^2 > size of the ORIGINAL set 
        for (int i = 0; i <= b.length(); i++) {
            if (i%p == 0) { // if it's a multiple of p
                b.set(i, false); // set it to false (not prime)
            }
        }
        p = b.nextSetBit(p); // Make p = first bit that is set to true starting after the previous p index.
    }
    return b;
}

/**
 * @param args
 */
public static void main(String[] args) {

    int set = 2000000;

    BitSet bits = new BitSet(set);
    for (int i = 0; i < set; i++) {
        bits.set(i); // set all bits to True; when you print only the true ones print out
    }
    BitSet primeBits = new BitSet(set);
    primeBits = findPrimes(2, bits, set);
    //System.out.println("List of primes: " + primeBits);

    BigInteger sum = BigInteger.ZERO;
    for (int j = 0; j <= primeBits.length(); j++) {
        if (primeBits.get(j) == true ) {
            sum = sum.add(BigInteger.valueOf(j));
        }
    }

    System.out.println("Sum is: " + sum); // I get 142,913,687,247 which is 141,675 too small (142913828922)
}

}
4

3 回答 3

2 
    while (p*p < s) {  // repeat until p^2 > size of the ORIGINAL set 
        for (int i = 0; i <= b.length(); i++) {
            if (i%p == 0) { // if it's a multiple of p
                b.set(i, false); // set it to false (not prime)
            }
        }
        p = b.nextSetBit(p);
        // Make p = first bit that is set to true starting after the previous p index.
    }

将素数的所有倍数标记p为合数，包括p它自己。所以只有大于极限平方根的素数仍然没有标记。

  • 该方法使用埃拉托色尼筛

不，它没有。它使用审判部门。你将每个数除以所有小于极限平方根的素数，然后检查余数是否为 0。

循环应该是

for(int i = p*p; i < b.length; i += p)
    b.set(i,false);

实施埃拉托色尼筛法。

于 2013-06-11T19:44:34.657 回答
1

您的解决方案不是埃拉托色尼筛法，而是试验师；模运算符给出了它。这是一个适当的埃拉托色尼筛法的伪代码，它将找到的素数相加：

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

我将把代码翻译成 Java 留给你。如果您对使用素数编程感兴趣，我在我的博客上谦虚地推荐这篇文章，其中包括 Java 中的 Eratosthenes 筛选。那里的代码还将帮助您解决其他一些 Project Euler 问题。

于 2013-06-11T20:38:57.357 回答
0 
for (int i = 0; i <= b.length(); i++)

将其更改为

for (int i = p+1; i <= b.length(); i++)

否则，您将消除所有小于 2,000,000^.5 的素数

于 2013-06-11T19:44:12.453 回答