streamalism.org

1. Introduktion

I denne vejledning viser vi forskellige måder, hvorpå vi kan generere primtal ved hjælp af Java.

Hvis du ønsker at kontrollere, om et tal er prime - her er en hurtig guide til, hvordan du gør det.

2. Primtal

Lad os starte med kernedefinitionen. Et primtal er et naturligt tal, der er større end et, der ikke har andre positive skiller end det ene og sig selv.

For eksempel er 7 primær, fordi 1 og 7 er dens eneste positive heltal, mens 12 ikke er, fordi den har divisorerne 3 og 2 ud over 1, 4 og 6.

3. Generering af primtal

I dette afsnit ser vi, hvordan vi effektivt kan generere primtal, der er lavere end en given værdi.

3.1. Java 7 og før - Brute Force

offentlig statisk liste primeNumbersBruteForce (int n) {List primeNumbers = new LinkedList (); for (int i = 2; i <= n; i ++) {hvis (isPrimeBruteForce (i)) {primeNumbers.add (i); }} returner primtal } offentlig statisk boolsk isPrimeBruteForce (int-nummer) {for (int i = 2; i <nummer; i ++) {hvis (nummer% i == 0) {returner false; }} returner sandt; } 

Som du kan se, primeNumbersBruteForce er iterering over numrene fra 2 til n og blot kalde isPrimeBruteForce () metode til at kontrollere, om et tal er prime eller ej.

Metoden kontrollerer hver taldelelighed med tallene i et interval fra 2 til nummer 1.

Hvis vi på et eller andet tidspunkt støder på et tal, der er deleligt, returnerer vi falsk. I slutningen når vi finder ud af, at tallet ikke kan deles med noget af dets forrige tal, returnerer vi sand, hvilket indikerer, at det er et primtal.

3.2. Effektivitet og optimering

Den tidligere algoritme er ikke lineær og har tidskompleksiteten O (n ^ 2). Algoritmen er heller ikke effektiv, og der er tydeligvis et rum til forbedring.

Lad os se på tilstanden i isPrimeBruteForce () metode.

Når et tal ikke er et primtal, kan dette tal indregnes i to faktorer, nemlig -en og b dvs. nummer = a * b. Hvis begge dele -en og b var større end kvadratroden af n, a * b ville være større end n.

Så mindst en af ​​disse faktorer skal være mindre end eller lig med kvadratroden af ​​et tal, og for at kontrollere om et tal er prime, behøver vi kun at teste for faktorer, der er lavere end eller lig med kvadratroden af ​​det nummer, der kontrolleres.

Primtal kan aldrig være et lige antal, da lige tal alle kan deles med 2.

Derudover kan primtal aldrig være et lige antal, da lige tal alle kan deles med 2.

Husk ovenstående ideer, lad os forbedre algoritmen:

offentlig statisk liste primeNumbersBruteForce (int n) {List primeNumbers = new LinkedList (); hvis (n> = 2) {primeNumbers.add (2); } for (int i = 3; i <= n; i + = 2) {hvis (isPrimeBruteForce (i)) {primeNumbers.add (i); }} returner primtal } privat statisk boolsk isPrimeBruteForce (int-nummer) {for (int i = 2; i * i <antal; i ++) {hvis (antal% i == 0) {returner false; }} returner sandt; } 

3.3. Brug af Java 8

Lad os se, hvordan vi kan omskrive den tidligere løsning ved hjælp af Java 8-idiomer:

offentlig statisk liste primeNumbersTill (int n) {return IntStream.rangeClosed (2, n) .filter (x -> isPrime (x)). boxed () .collect (Collectors.toList ()); } privat statisk boolsk isPrime (int-nummer) {return IntStream.rangeClosed (2, (int) (Math.sqrt (number))). filter (n -> (n & 0X1)! = 0) .allMatch (n -> x% n! = 0); } 

3.4. Brug af sigte af eratosthenes

Der er endnu en effektiv metode, der kan hjælpe os med at generere primtal effektivt, og det hedder Sieve Of Eratosthenes. Dens tidseffektivitet er O (n logn).

Lad os se på trinnene i denne algoritme:

1. Opret en liste over fortløbende heltal fra 2 til n: (2, 3, 4,…, n)
2. Først lad s være lig 2, det første primtal
3. Startende fra s, tæl op i intervaller på s og marker hvert af disse tal større end s sig selv på listen. Disse tal vil være 2p, 3p, 4p osv .; bemærk, at nogle af dem muligvis allerede er blevet markeret
4. Find det første tal større end s på listen, der ikke er markeret. Hvis der ikke var noget sådant nummer, skal du stoppe. Ellers lad s svarer nu til dette nummer (som er den næste primære), og gentag fra trin 3

I slutningen, når algoritmen slutter, er alle de tal på listen, der ikke er markeret, primtalene.

Sådan ser koden ud:

public static List sieveOfEratosthenes (int n) {boolean prime [] = new boolean [n + 1]; Arrays. Fyld (prime, true); for (int p = 2; p * p <= n; p ++) {hvis (prime [p]) {for (int i = p * 2; i <= n; i + = p) {prime [i] = falsk; }}} Liste primNumre = ny LinkedList (); for (int i = 2; i <= n; i ++) {if (prime [i]) {primeNumbers.add (i); }} returner primtal } 

3.5. Arbejdseksempel på sigte af eratosthenes

Lad os se, hvordan det fungerer for n = 30.

Overvej billedet ovenfor, her er passerne fra algoritmen:

1. Sløjfen starter med 2, så vi efterlader 2 umærket og markerer alle delene på 2. Den er markeret i billedet med den røde farve
2. Sløjfen bevæger sig til 3, så vi efterlader 3 umærket og markerer alle delere af 3, der ikke allerede er markeret. Det er markeret i billedet med den grønne farve
3. Loop flytter til 4, den er allerede markeret, så vi fortsætter
4. Loop bevæger sig til 5, så vi efterlader 5 umærket og markerer alle delere af 5, der ikke allerede er markeret. Det er markeret i billedet med den lilla farve
5. Vi fortsætter over trin, indtil sløjfen nås lig med kvadratroden af n

4. Konklusion

I denne hurtige vejledning illustrerede vi måder, hvorpå vi kan generere primtal indtil 'N' -værdien.

Implementeringen af ​​disse eksempler findes på GitHub.