Comment optimiser l'algorithme pour pouvoir déterminer les nombres premiers longs de 10 chiffres en Java

Question

Je suis actuellement nouveau à java et à la programmation en général, je travaille sur un algorithme qui détermine les nombres premiers dans des gammes données spécifiques. Actuellement, il fonctionne avec six gammes qui sont des nombres inférieurs à 1 milliard, quand j'ai essayé de déterminer un nombre long de 10 chiffres, il a échoué. Je suis conscient qu'il doit être changé depuis longtemps car le chiffre est hors de portée, mais je ne suis pas sûr de savoir comment.

c'est la partie du code où il détermine si le umber est premier:

public ArrayList<Integer> getPrimes(int StartPos, int n) { 
    ArrayList<Integer> primeList = new ArrayList<>(); 

    boolean[] primes = new boolean[n + 1]; 
    for (int i = StartPos; i < primes.length; i++) { 
     primes[i] = true; 
    } 
    int num = 2; 
    while (true) { 
     for (int i = 2;; i++) { 
       int m = num * i; 
       if (m > n) { 
        break; 
       } else { 
        primes[m] = false; 
       } 
     } 
     boolean nextNum = false; 
     for (int i = num + 1; i < n + 1; i++) { 
       if (primes[i]) { 
        num = i; 
        nextNum = true; 
        break; 
       } 
     } 
     if (!nextNum) { 
       break; 
     } 
    } 
    for (int i = 0; i < primes.length; i++) { 
     if (primes[i]) { 
      primeList.add(i);   
     }  
    } 
    return primeList; 
} 

Je vérifiais en ligne et trouvé que peut-être que je pourrais le faire avec des vecteurs mais je n'ai aucune expérience avec eux et aussi ils sont relativement plus lents qu'un tableau.

Answer 1

Vous pouvez essayer BigInteger # isProbablePrime: https://www.tutorialspoint.com/java/math/biginteger_isprobableprime.htm

import java.math.BigInteger; 
import java.util.List; 
import java.util.stream.Collectors; 
import java.util.stream.LongStream; 

// Java 8 
public class FindPrimes { 
    public static void main(String[] args) { 
     System.out.println("1 - 100 primes: " + findPrimes(1L, 99L)); 
     System.out.println("some 10-digit primes: " + findPrimes(99_999_999_999L, 20000L)); 
    } 

    private static List<Long> findPrimes(long start, long quant) { 
     return LongStream.rangeClosed(start, start + quant).filter(v -> 
       BigInteger.valueOf(v).isProbablePrime(1)).boxed().collect(Collectors.toList()); 
    } 
} 

Answer 2

Vous dites que vous apprenez, donc je vais vous donner un aperçu de pseudocode, pas la réponse.

En général, la méthode pour trouver un choix dans une gamme est:

repeat 
    pick a number in the range 
until (the number is prime) 

Vous voulez un numéro à dix chiffres. Une façon de générer un candidat tout en évitant les non-primes évidentes est:

start with digit in [1..9] // No leading zero. 
repeat 8 times 
    append a digit in [0..9] 
endrepeat 
append a digit in [1, 3, 7, 9] // Final digits for large primes. 

Cela vous donnera un nombre premier de dix chiffres possible.

Maintenant, vous devez tester pour vérifier qu'il est premier.

Il existe des tests comme Miller-Rabin que vous pouvez essayer, mais probablement pas si vous êtes un vrai débutant. Je suggère de mettre en place un tamis d'Eratosthenes couvrant les nombres jusqu'à 10.000 qui est la racine carrée de votre limite supérieure de 10.000.000.000. Cela vous donnera un accès rapide à tous les nombres premiers sous la racine carrée de votre nombre. Configurez le tamis une seule fois au début de votre programme. Faites-en une classe distincte et incluez une méthode int nextPrime(int n) qui renvoie l'élément suivant après le paramètre fourni. Une fois que c'est en place, alors vous pouvez écrire une méthode de division d'essai pour tester votre numéro à dix chiffres:

boolean method isPrime(tenDigitNumber) 
    testPrime <- 2 
    limit <- square root of tenDigitNumber // Only calculate this once. 
    while (testPrime < limit) 
    if (tenDigitNumber MOD testPrime == 0) 
     return false // Number is not prime. 
    else 
     testPrime <- sieve.nextPrime(testPrime) 
    endif 
    endwhile 
    return true // If we get here then the number is prime. 
end isPrime 

Parce que vous avez mis en place le tamis à l'avance, cela devrait fonctionner assez rapidement. Si c'est trop lent, alors il est temps d'envisager de coder Miller-Rabin ou l'une des autres méthodes d'essai de premier ordre.

En plus de la classe Sieve of Eratosthenes, une autre méthode utilitaire utile est une méthode iSqrt() qui renvoie une racine carrée entière. Ma propre version utilise la méthode de Newton-Raphson, bien qu'il y ait sans doute d'autres possibilités.