0

我正在尝试解决 Project Euler 的第 10问题,但由于某种原因,我无法正确解决。我在编程和 Java 方面真的很陌生,所以我不明白为什么它不起作用。问题的重点是找出所有低于 2,000,000 的素数之和。

/*  The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

    Find the sum of all the primes below two million.
*/  

public static void main(String[] args){

    long n = 1;
    long sum = 0;
    long limit;

    System.out.println("Enter the limit of n: ");
    limit = TextIO.getlnLong(); //TextIO is another input method
    while (limit <= 0){
        System.out.println("Enter the limit of n (must be positive): ");
        limit = TextIO.getlnLong();

    }       

    while (n < limit){ 
        n++;
        if (n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && n % 7 != 0 && n != 1 || n == 2 || n == 3 || n == 5 || n == 7){ //this is my prime checking method, might be flawed

            sum = sum + n;  
            System.out.println(+sum);
        } //end if

    }//end while

    System.out.println("The sum of the primes below 2,000,000 is: " +sum);

} //end of main
4

5 回答 5

4

如需有效的素数检查方法,请阅读埃拉托色尼筛

于 2012-06-07T21:39:54.120 回答
2

你的主要方法坏了。如果一个数在 2 和该数的平方根之间没有任何除数,则该数是素数。13*13 将通过您的主要检查功能。

for i to sqrt(n):
   if(n % i == 0):
       OH NO NOT PRIME DO SOMETHING HERE?
if something is prime
   add some stuff
于 2012-06-07T21:40:09.123 回答
1

这里有 2 个比普通解决方案更好的解决方案:

1)遍历奇数(唯一的偶素数已经在总和中)并检查它们是否是素数:

private static boolean isOddPrime(int x) {
    for ( int i = 3 ; i*i <= x ; i+=2 ){ 
        if ( x % i == 0 ) {
            return false;
        }
    }
    return true;
}

private static void sumOfPrimes1(int n) {       
    long sum = 2;
    for ( int i = 3 ; i < n ; i+=2 ) {
        if ( isOddPrime(i) ) {
            sum+=i;
        }
    }
    System.out.println(sum); 
}

2)使用埃拉托色尼筛

private static void sumOfPrimes2(int n) {
    boolean notPrimes[] = new boolean[n];   // default = false
    for ( int i = 2 ; i*i < n ; i++ ) {
        if ( !notPrimes[i] ) {
            for ( int j = i*i ; j < n ; j+=i ){
                notPrimes[j] = true;
            }
        }
    }
    long sum = 2 ;
    for ( int i = 3 ; i < n ; i+=2 ) {
        if ( !notPrimes[i] ) {
            sum+=i;
        }
    }
    System.out.println(sum);
}

我使用“notPrimes”(复合)而不是“primes”作为数组,只是为了利用 Java 中的默认布尔值是false.

性能

n           |    2000000        8000000       16000000
------------+-------------------------------------------
Solution 1  |    1309 ms        8574 ms       22757 ms
Solution 2  |    119 ms         696 ms        1624 ms
于 2014-11-12T21:23:18.443 回答
0

http://www.counton.org/explorer/primes/checking-if-a-number-is-prime/

检查数字 N 是否为素数的一个捷径是,我们不必依次尝试从 2 到 N(2、3、4、5、6 ...... N。

exp :因为 3 是 18 的因数,并且 18/3=6,所以 18=3x6。我们只需要测试较小的数字 3,看看它是不是 18 的因数,而不是 6。同样,5 是 20 的因数,20=5x4,所以我们只需要测试较小的数 4 作为因数。但是如果我们不知道一个数的因数怎么办?因此,测试一个数字是否为素数意味着我们只需要测试“较小”的因素。但是较小的因素在哪里停止而较大的因素从哪里开始呢?这里的原理是:假设一个数是 N 的因数,并且它小于数 N 的平方根,那么第二个因数必须大于平方根。我们可以通过上面的例子看到这一点:对于 18,我们只需要测试直到 18 的平方根即 4.243 的数字,即最多 4!这比测试 17 以内的所有数字要快得多!!25岁,

public static void main(String[] args) {
    long sum = 0;
    for (int i = 2; i < 2000000; i++) {
        if (isPrime(i)) {
            sum += i;
        }
    }
    System.out.println(sum);
}

// check if a number is prime
private static boolean isPrime(int number) {
    int sqrt = (int) Math.sqrt(number);
    boolean isPrime = true;

   // test up to square root of the number
   for (int i = 2; i <= sqrt; i++) {
        if (number % i == 0) {
            isPrime = false;
            break;
        }
    }
    return isPrime;
}
于 2019-10-02T13:37:03.767 回答
-4
public static void main(String args[])
{
  long n = 1;
  long sum = 0;
  long limit=Integer.parseInt(args[0]);

  while (n < limit)
  {
    n++;
    if(n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && n % 7 != 0 && n != 1 || n == 2 || n == 3 || n == 5 || n == 7)
    {
      sum = sum + n;
    }
  }


    System.out.println("The sum of the prime numbers = " +sum);
 }
于 2012-11-02T17:54:34.257 回答