Generovanie prvočísel v Jave

1. Úvod

V tomto výučbe si ukážeme rôzne spôsoby, ako môžeme generovať prvočísla pomocou Javy.

Ak chcete skontrolovať, či je číslo prvočíslo - tu je stručný návod, ako to urobiť.

2. Prvočísla

Začnime základnou definíciou. Prvočíslo je prirodzené číslo väčšie ako jedno, ktoré nemá kladných deliteľov okrem jedného a seba samého.

Napríklad 7 je prvočíslo, pretože 1 a 7 sú jeho jedinými pozitívnymi celočíselnými faktormi, zatiaľ čo 12 nie je preto, že má okrem 1, 4 a 6 aj delitele 3 a 2.

3. Generovanie prvočísel

V tejto časti uvidíme, ako môžeme efektívne generovať prvočísla, ktoré sú nižšie ako zadaná hodnota.

3.1. Java 7 a Before - Brute Force

public static Zoznam primeNumbersBruteForce (int n) {List primeNumbers = new LinkedList (); pre (int i = 2; i <= n; i ++) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} vrátiť prvočísla; } public static boolean isPrimeBruteForce (int number) {for (int i = 2; i <number; i ++) {if (number% i == 0) {return false; }} návrat true; } 

Ako môžeš vidieť, primeNumbersBruteForce iteruje nad číslami od 2 do n a jednoducho zavolať na isPrimeBruteForce () metóda na kontrolu, či je číslo prvočíslo alebo nie.

Metóda kontroluje deliteľnosť každého čísla číslami v rozsahu od 2 do číslo 1.

Ak v ktoromkoľvek okamihu narazíme na číslo, ktoré je deliteľné, vrátime hodnotu false. Na konci, keď zistíme, že číslo nie je deliteľné žiadnym z jeho predchádzajúcich čísel, vrátime hodnotu true, ktorá označuje jeho prvočíslo.

3.2. Efektívnosť a optimalizácia

Predchádzajúci algoritmus nie je lineárny a má časovú zložitosť O (n ^ 2). Algoritmus tiež nie je efektívny a jednoznačne existuje priestor na zlepšenie.

Pozrime sa na stav v isPrimeBruteForce () metóda.

Ak číslo nie je prvočíslo, možno ho rozdeliť do dvoch faktorov, a to a a b t.j. číslo = a * b. Ak oboje a a b boli väčšie ako druhá odmocnina z n, a * b by bol väčší ako n.

Aspoň jeden z týchto faktorov teda musí byť menší alebo rovný druhej odmocnine čísla a aby sme skontrolovali, či je číslo prvočíslo, musíme testovať iba faktory menšie alebo rovné druhej odmocnine kontrolovaného čísla.

Prvočísla nikdy nemôžu byť párne čísla, pretože párne čísla sú deliteľné 2.

Prvočísla navyše nikdy nemôžu byť párnym číslom, pretože párne čísla sú deliteľné 2.

Nezabudnite na vyššie uvedené nápady a vylepšime algoritmus:

public static Zoznam primeNumbersBruteForce (int n) {List primeNumbers = new LinkedList (); if (n> = 2) {primeNumbers.add (2); } for (int i = 3; i <= n; i + = 2) {if (isPrimeBruteForce (i)) {primeNumbers.add (i); }} vrátiť prvočísla; } private static boolean isPrimeBruteForce (int number) {for (int i = 2; i * i <number; i ++) {if (number% i == 0) {return false; }} návrat true; } 

3.3. Používanie Java 8

Pozrime sa, ako môžeme prepísať predchádzajúce riešenie pomocou idiómov Java 8:

public static List primeNumbersTill (int n) {return IntStream.rangeClosed (2, n) .filter (x -> isPrime (x)). boxed () .collect (Collectors.toList ()); } private static boolean isPrime (int number) {return IntStream.rangeClosed (2, (int) (Math.sqrt (number))) .filter (n -> (n & 0X1)! = 0) .allMatch (n -> x% n! = 0); } 

3.4. Pomocou sitka Eratosthenes

Existuje ešte ďalšia efektívna metóda, ktorá by nám mohla pomôcť efektívne generovať prvočísla, a volá sa Sieve Of Eratosthenes. Jeho časová účinnosť je O (n logn).

Pozrime sa na kroky tohto algoritmu:

  1. Vytvorte zoznam po sebe nasledujúcich celých čísel od 2 do n: (2, 3, 4, ..., n)
  2. Spočiatku nechajme p byť rovné 2, prvé prvočíslo
  3. Začať z p, počítať v prírastkoch p a každé z týchto čísel označte väčším ako p v zozname. Tieto čísla budú 2p, 3p, 4p atď .; Upozorňujeme, že niektoré z nich už mohli byť označené
  4. Nájdite prvé číslo väčšie ako p v zozname, ktorý nie je označený. Ak také číslo nebolo, prestaňte. Inak nechajme p teraz rovná sa toto číslo (čo je ďalšia prvočíslo) a opakujte od kroku 3

Na konci, keď sa algoritmus ukončí, sú všetky čísla v zozname, ktoré nie sú označené, prvočísla.

Takto vyzerá kód:

public static List sieveOfEratosthenes (int n) {boolean prime [] = new boolean [n + 1]; Arrays.fill (prime, true); pre (int p = 2; p * p <= n; p ++) {if (prime [p]) {for (int i = p * 2; i <= n; i + = p) {prime [i] = nepravda; }}} Zoznam prvočísel = nový LinkedList (); pre (int i = 2; i <= n; i ++) {if (prime [i]) {primeNumbers.add (i); }} vrátiť prvočísla; } 

3.5. Pracovný príklad sita Eratosthenes

Pozrime sa, ako to funguje pre n = 30.

Pozrime sa na obrázok vyššie, tu sú kroky, ktoré vykonal algoritmus:

  1. Smyčka začína na 2, takže ponecháme 2 neoznačené a označíme všetky delitele 2. Je to na obrázku označené červenou farbou
  2. Smyčka sa presunie na 3, takže ponecháme 3 neoznačené a označíme všetky delitele 3, ktoré ešte nie sú označené. Je to na obrázku označené zelenou farbou
  3. Smyčka sa posúva na 4, je už označená, takže pokračujeme
  4. Smyčka sa presunie na 5, takže ponecháme 5 neoznačených a označíme všetky delitele 5, ktoré ešte nie sú označené. Na obrázku je to označené fialovou farbou
  5. Pokračujeme vyššie uvedenými krokmi, kým sa nedosiahne slučka, ktorá sa rovná druhej odmocnine z n

4. Záver

V tomto rýchlom výučbe sme ilustrovali spôsoby, ako môžeme generovať prvočísla až do hodnoty „N“.

Implementáciu týchto príkladov možno nájsť na GitHub.


$config[zx-auto] not found$config[zx-overlay] not found