Un moyen plus efficace pour cela?

Question

Je me demande s'il existe un moyen plus efficace d'exécuter ce programme? Il fonctionne bien pour les nombres inférieurs, mais au fur et à mesure que vous augmentez, le temps augmente de façon exponentielle. Donc un nombre comme 1000000 prend une éternité (ne le laisse jamais finir donc je ne connais pas le temps). Toute aide serait appréciée.

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

Il y a de meilleurs algorithmes prime la recherche, mais comme une solution rapide, il vous suffit de tester les facteurs à travers la racine carrée du nombre actuel, parce que si vous trouvez un facteur au-dessus de la racine carrée, alors vous aurait dû trouver un facteur en dessous de la racine carrée.

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

De plus, sortir de la boucle et revenir false si vous avez trouvé un facteur et prouvé ainsi le composite numérique.

Si plus d'efficacité est souhaitée, vous pouvez implémenter le Sieve of Eratosthenes afin de ne vérifier que les facteurs possibles eux-mêmes.

Answer 2

Vous devriez vraiment stocker un ensemble de nombres premiers chaque fois que vous en trouvez un, de sorte que vous évitiez de diviser par tous les nombres à chaque fois.

Cette chose: currentNum % 2 != 0 peut s'écrire currentNum & 1.

Aussi votre algorithme est faux, essayez d'en donner 3 en entrée.

Answer 3

Utilisez Eratosthenes Sievie: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Vous trouverez tous les nombres premiers ci-dessous nombre donné dans O (n log n log n) et vous devrez aller une fois sur toute la table.

Answer 4

j'avais écrit un.je ne peux pas m'assurer que tout est correct.J'ai testé 1000000 dans ma machine, il a juste pris 31 ms. la mémoire nécessite: 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; 
} 

}