Более эффективный способ для этого?

Question

Мне интересно, есть ли более эффективный способ запуска этой программы? Он работает отлично для более низких чисел, но по мере увеличения, так же время - экспоненциально. Таким образом, число, подобное 1000000, берет навсегда (никогда не позволяйте этому закончить, поэтому я не знаю времени). Любая помощь будет оценена по достоинству.

import java.util.*; 

public class SumOfPrimes { 

public static void main(String args[]) { 
    Scanner in = new Scanner(System.in); 
    long number = 0; 

    System.out.println("This program outputs the sum of the primes of a given number."); 
    System.out.print("Please enter a number: "); 
    number = in.nextLong(); 

    System.out.println("The sum of the primes below "+number+" is: "+sumOfPrimes(number)); 
} 

public static long sumOfPrimes(long n){ 
    long currentNum = 2; 
    long sum = 0; 
    if (n > 2){ 
     sum = sum + 2; 
    } 

    while (currentNum <= n) { 
     if (currentNum % 2 != 0 && isPrime(currentNum)) { 
      sum = sum + currentNum; 
     } 
     currentNum++; 
    } 
return sum; 
} 

public static boolean isPrime(long currentNum){ 
    boolean primeNumber = true; 

    for (long test = 2; test < currentNum; test++) { 
     if ((currentNum % test) == 0){ 
      primeNumber = false; 
     } 
    } 

return primeNumber; 
} 
} 

Answer 1

Есть более простой ознакомительную алгоритмы, но как быстро исправить, вам нужно только проверить факторы через квадратный корень из текущего номера, потому что если вы нашли фактор выше квадратного корня, то вам должен был найти коэффициент ниже квадратного корня.

long stop = (long) Math.sqrt(currentNum); 
for (long test = 2; test <= stop ; test++) { 

Кроме того, выйти из цикла и возврата false если вы нашли фактор и, таким образом, доказано число композит.

Если требуется более высокая эффективность, вы можете реализовать Sieve of Eratosthenes так, чтобы вы проверяли только возможные факторы, которые сами по себе являются основными.

Answer 2

Вы действительно должны хранить набор простых чисел каждый раз, когда найдете его, поэтому вы избегаете деления на все числа каждый раз.

Эта вещь: currentNum % 2 != 0 может быть написана как currentNum & 1.

Также ваш алгоритм ошибочен, попробуйте дать 3 в качестве входных данных.

Answer 3

Использование Eratosthenes Sievie: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Вы найдете все простые числа ниже заданного числа в O (n log n log n), и вам нужно будет пройти один раз над всей таблицей.

Answer 4

Я написал один. Я не могу убедиться, что все правильно. Я проверил 1000000 на моей машине, это всего лишь 31 мс. память требуется: 1000000 * 1bytes = 1MB

public class FindPrime { 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    long begin=System.currentTimeMillis(); 
    System.out.println(findPrime(1000000)); 

    System.out.println("cost time="+(System.currentTimeMillis()-begin)+"ms"); 

} 

public static long findPrime(int max){ 
    boolean data[]=new boolean[max+1]; 
    long sum=0; 
    int stop=(int) Math.sqrt(max); 
    for(int i=2;i<=stop;i++){ 
     if(data[i]==false){ 
      sum+=i; 

      int index=i+i; 
      while(index<=max){ 
       data[index]=true; 
       index=index+i; 
      } 
      //System.out.println(i); 
     } 
    } 

    stop=stop+1; 

    for(;stop<=max;stop++){ 
     if(data[stop]==false){ 
      sum+=stop; 
      //System.out.println(stop); 
     } 
    } 

    return sum; 
} 

}