Takiego sita jak np. to poniżej.
Jak widać metoda przeliczSito jest banalnie prosta i bardzo szybka. Zawiera tylko (number - 2) dzieleń całkowitych, reszta to same dodawania. Czas policzenia największej liczby pierwszej jest jednocześnie czasem policzenia wszystkich mniejszych od niej, więc po policzeniu największej dane są wypluwane taśmowo (liczy się tylko czas dostępu do tablicy BitSet). Ponieważ informacja o każdej liczbie zajmuje tylko 1 bit, więc jest również najbardziej optymalna pamięciowo.
Można też uzyskać informację o liczbie znalezionych liczb pierwszych, ponieważ jest to liczba zgaszonych bitów w tablicy "podzielna". BitSet udostępnia liczbę bitów ustawionych oraz największy ustawiony, więc łatwo policzyć zgaszone.
package com.olamagato.util;
import java.util.BitSet;
/**
* Pozwala szybko wyszukać 32-bitowe liczby pierwsze.
* Wersja lokalna, jednowątkowa, niesynchronizowana.
* Optymalna jest globalna, wielowątkowa (ForkJoinTask), synchronizowana
* Do policzenia Integer.MAX_VALUE potrzeba
* 256 MB + 32 bajty pamięci JVM oraz dwie kawy.
* @author Olamagato
*/
public class FreePrimes
{
public FreePrimes(final int maxNumber)
{
this.podzielna = new BitSet(maxNumber);
init();
}
public FreePrimes()
{
this.podzielna = new BitSet();
init();
}
private void init()
{
podzielna.set(0, 1);
największaPoliczona = 3;
}
/**
* Informuje czy liczba jest pierwsza.
* W tym celu przelicza lub dolicza sito Erastotenesa
* od największaPoliczona do number.
* @param number liczba do sprawdzenia
* @return true jeżeli number jest liczbą pierwszą
*/
public boolean isPrime(final int number)
{
if(number > największaPoliczona)
przeliczSito(number);
return !podzielna.get(number);
}
/**
* Zwraca największą liczbę pierwszą nie większą niż number lub -1.
* Jeżeli number jest liczbą pierwszą to jest ona zwracana jako wynik.
* @param number górny zakres sprawdzanego zbioru liczb pierwszych
* @return największa liczba pierwsza z zakresu [2, number] lub -1
*/
public int getLargestPrime(final int number)
{ //nowa metoda BitSet.previousClearBit() dodana w Javie 1.7
return isPrime(number) ? number : podzielna.previousClearBit(number);
}
/**
* Uzupełnia sito przez wykreślenie wielokrotności licz od
* number do największaPoliczona.
* Wersja jednowątkowa.
* @param number liczba, do której przeliczane jest sito
*/
private void przeliczSito(final int number)
{ //dokłada brakujące skreślenia od największaPoliczona do number
for(int skreśl = 2; skreśl <= number ; ++skreśl)
{ //skreśla tylko wielokrotności liczby do skreślania zaczynając
//od największaPoliczona (omija wcześniejsze skreślenia)
final int liczOd = największaPoliczona >= skreśl ?
największaPoliczona - największaPoliczona % skreśl : skreśl;
//skreśla kolejne wielokrotności
for(int n = liczOd + skreśl; n <= number; n += skreśl)
podzielna.set(n);
}
największaPoliczona = number;
}
/**
* Bit zawierający false oznacza liczbę pierwszą, true oznacza
* wykreślony mnożnik. Liczby 0 i 1 muszą być ustawione jako true
* z definicji.
*/
private final BitSet podzielna;
private int największaPoliczona; //największa dotychczas policzona
//testy
public static void main(String[] args)
{
final int PR = 15485857; //spora liczba pierwsza
int[] testy = { 18, 40, 97, 100, PR, 16_000_000, 18_000_000 };
FreePrimes pierwsze = new FreePrimes(32_000_00);
for(int i: testy)
test(pierwsze, i);
}
@SuppressWarnings("UseOfSystemOutOrSystemErr")
private static void test(FreePrimes primes, int liczba)
{
Boolean isPrime = Boolean.valueOf(primes.isPrime(liczba));
System.out.printf("Czy %d jest pierwsza? %s",
liczba, isPrime ? "Tak" : "Nie");
if(!isPrime)
System.out.printf(", największa liczba pierwsza <= %d to %d",
liczba, primes.getLargestPrime(liczba));
System.out.println();
}
}
Output:
Czy 18 jest pierwsza? Nie, największa liczba pierwsza <= 18 to 17
Czy 40 jest pierwsza? Nie, największa liczba pierwsza <= 40 to 37
Czy 97 jest pierwsza? Tak
Czy 100 jest pierwsza? Nie, największa liczba pierwsza <= 100 to 97
Czy 15485857 jest pierwsza? Tak
Czy 16000000 jest pierwsza? Nie, największa liczba pierwsza <= 16000000 to 15999989
Czy 18000000 jest pierwsza? Nie, największa liczba pierwsza <= 18000000 to 17999987