streamalism.org

1. Introduksjon

I denne veiledningen viser vi forskjellige måter vi kan generere primtall på ved hjelp av Java.

Hvis du ønsker å sjekke om et tall er prime - her er en rask guide til hvordan du gjør det.

2. Primtall

La oss starte med kjernedefinisjonen. Et primtall er et naturlig tall som er større enn ett som ikke har andre positive skiller enn det ene og seg selv.

For eksempel er 7 primær fordi 1 og 7 er de eneste positive heltallfaktorene, mens 12 ikke er fordi den har delene 3 og 2 i tillegg til 1, 4 og 6.

3. Generere primtall

I denne delen ser vi hvordan vi effektivt kan generere primtall som er lavere enn en gitt verdi.

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 ++) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} returner primtall; } offentlig statisk boolsk isPrimeBruteForce (int-nummer) {for (int i = 2; i <number; i ++) {if (number% i == 0) {return false; }} returner sant; } 

Som du kan se, primeNumbersBruteForce gjentas over tallene fra 2 til n og bare ringe isPrimeBruteForce () metode for å sjekke om et tall er primtall eller ikke.

Metoden sjekker hvert tall som kan deles med tallene i et område fra 2 til nummer-1.

Hvis vi på et tidspunkt støter på et tall som kan deles, returnerer vi falske. På slutten når vi finner ut at tallet ikke kan deles med noe av det forrige tallet, returnerer vi sant, noe som indikerer at det er et primtall.

3.2. Effektivitet og optimalisering

Den forrige algoritmen er ikke lineær og har tidskompleksiteten til O (n ^ 2). Algoritmen er heller ikke effektiv, og det er tydeligvis et rom for forbedring.

La oss se på tilstanden i isPrimeBruteForce () metode.

Når et tall ikke er et primtall, kan dette tallet regnes inn i to faktorer, nemlig en og b dvs. Nummer = a * b. Hvis begge deler en og b var større enn kvadratroten av n, a * b ville være større enn n.

Så minst en av disse faktorene må være mindre enn eller lik kvadratroten til et tall, og for å sjekke om et tall er prime, trenger vi bare å teste for faktorer som er lavere enn eller lik kvadratroten til tallet som blir sjekket.

Primtall kan aldri være et partall da alle tall kan deles med 2.

I tillegg kan primtall aldri være et partall, ettersom partall er alle delbare med 2.

Med tankene ovenfor ideene, la oss 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) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} returner primtall; } privat statisk boolsk isPrimeBruteForce (int-nummer) {for (int i = 2; i * i <number; i ++) {if (number% i == 0) {return false; }} returner sant; } 

3.3. Bruke Java 8

La oss se hvordan vi kan omskrive den forrige løsningen ved hjelp av Java 8-uttrykk:

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. Bruke Sieve of Eratosthenes

Det er enda en effektiv metode som kan hjelpe oss med å generere primtall effektivt, og det kalles Sieve Of Eratosthenes. Tidseffektiviteten er O (n logn).

La oss ta en titt på trinnene i denne algoritmen:

1. Lag en liste over påfølgende heltal fra 2 til n: (2, 3, 4,…, n)
2. I utgangspunktet, la s være lik 2, det første primtallet
3. Starter fra s, tell opp i trinn på s og merk hvert av disse tallene større enn s seg selv i listen. Disse tallene vil være 2p, 3p, 4p, etc .; Vær oppmerksom på at noen av dem allerede har blitt merket
4. Finn det første tallet som er større enn s i listen som ikke er merket. Hvis det ikke var noe slikt nummer, stopp. Ellers la s nå lik dette tallet (som er neste primtall), og gjenta fra trinn 3

På slutten når algoritmen avsluttes, er alle tallene i listen som ikke er merket primtall.

Slik ser koden ut:

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

3.5. Arbeidseksempel på sil av eratosthenes

La oss se hvordan det fungerer for n = 30.

Tenk på bildet ovenfor, her er passene som algoritmen har gjort:

1. Sløyfen begynner med 2, så vi lar 2 umerkes og merker alle delene på 2. Den er merket i bildet med den røde fargen
2. Sløyfen beveger seg til 3, så vi lar 3 umerkes og merker alle delene av 3 som ikke allerede er merket. Det er merket i bildet med den grønne fargen
3. Loop beveger seg til 4, den er allerede merket, så vi fortsetter
4. Loop beveger seg til 5, så vi lar 5 umerkes og merker alle delene av 5 som ikke allerede er merket. Det er merket i bildet med den lilla fargen
5. Vi fortsetter over trinn til løkken er nådd lik kvadratroten av n

4. Konklusjon

I denne raske opplæringen illustrerte vi måter vi kan generere primtall til ‘N’ -verdien.

Implementeringen av disse eksemplene finner du på GitHub.