[Java] Trouvez le nombre premier avec le tamis Eratostenes (Partie 2)

introduction

Le code de publication précédente est un code coûteux qui "recherche toute la liste, la divise et la tamise" comme le souligne @swordone. Cela s'est avéré. Donc, sur la base de l'indice de @swordone, j'ai apporté une correction majeure au code.

code

Les différences avec le code précédent sont les suivantes.

• Changement de la liste de recherche de List <Integer> à boolean [].
• Au lieu de "liste de 2 à limite supérieure", "liste d'indices de 2 à limite supérieure" est utilisée.
• Tout d'abord, tous les éléments du tableau sont traités comme des nombres premiers (vrai), et lorsqu'ils sont éliminés, ils sont traités comme des valeurs non primaires (faux).
• Changé en "Accès aléatoire à l'élément de la valeur à filtrer et filtrer" au lieu de "Explorer la liste entière, diviser et tamiser".
• En augmentant l'incrément de l'instruction for par "augmenter de la valeur du premier courant (firstNum)" au lieu de "augmenter de 1", seuls les multiples du nombre premier courant (firstNum) sont éliminés.

PrimeNumberFinder.java

static void printPrimeNumbers2(int maxNumber) {

	//Étape 1: Mettez "entier de 2 à la limite supérieure" dans la liste de recherche.
	boolean[] targetNumbers = new boolean[maxNumber + 1];
	Arrays.fill(targetNumbers, true);
	targetNumbers[0] = false;
	targetNumbers[1] = false;

	//Liste des nombres premiers
	List<Integer> primeNumbers = new ArrayList<Integer>();

	int sqrt = (int) Math.sqrt(maxNumber);

	//Étape 3: Continuez l'opération de tamisage jusqu'à ce que la première valeur de la liste de recherche atteigne la racine carrée de l'argument.
	for(int i=2; i<=sqrt; i++) {
		//Étape 2: Faites du premier nombre de la liste de recherche un nombre premier et des multiples d'écran de la liste de recherche.
		//* Pour le moment, le numéro qui a déjà été exclu (faux) est exclu.
		int firstNum = i;
		if (targetNumbers[i]) {
			for (int j=i*firstNum; j<targetNumbers.length; j+=firstNum) {
				targetNumbers[j] = false;
			}
		}
	}

	//Étape 4: Déplacez les valeurs restantes dans la liste de recherche vers la liste des nombres premiers et terminez le processus.
	for (int i=2; i<targetNumbers.length; i++) {
		if (targetNumbers[i]) {
			primeNumbers.add(i);
		}
	}

	//Affichage des nombres premiers
	System.out.println(primeNumbers.stream().map(pNum -> pNum.toString()).collect(Collectors.joining("\t")));
}

Combien de temps cela a-t-il été?

• C'était plus de 10 fois plus rapide que le code précédent.
• Même si vous n'êtes pas le général Gillen, c'est une différence qui vous donne envie de dire: "N'est-ce pas écrasant, mon armée?"

Résumé

• Grâce à ce code, on m'a rappelé que le développement qui considère le "montant du calcul" est important.
• Je pense qu'il y a encore quelques points qui peuvent être améliorés avec ce code ...
• Merci @swordone pour tous les indices.