Sito Eratostenesa

0

Mam za zadanie stworzenie klasy SitoEratostenesa, ma ona posiadać konstruktor SitoEratostenesa(int n), który tworzy tablice boolowska odpowiedniego rozmiaru i oblicza na niej Sito Eratostenesa dla liczb od 2 do n.

Jak zaimplementować publiczną metodę boolean prime (int n), która ma zwracać true jeśli m jest pierwsza i false jeśli m nie jest pierwsza. Mam tutaj zapewne skorzystać z konstruktora SitoEratostenesa?

public class SitoEratostenesa
{   

     public SitoEratostenesa(int n)
    {

        boolean[] numbersTable = new boolean[n+1];
        for(int i = 2; i*i <= n; i++)
        {
            if (numbersTable[i] == true)
                continue;
            for (int j = 2 * i ; j <= n; j += i)
                numbersTable[j] = true;

        }
    }

        public static boolean prime(int m)
    {

    }
                public static void main(String[] args)
                {

                }

}
0

W temacie http://4programmers.net/Forum/Java/186553-liczbypierwsze-_java
W przedostatnim poście wrzuciłem całe źródło klasycznego sita.

0

a mógłbyś bardziej wyjaśnić to zadanie, które wrzuciłeś?

0

Tworzy sito, które potrzebujesz i pozwala sprawdzić czy dowolna liczba int jest pierwsza (isPrime()), a także jaka jest największa liczba pierwsza mniejsza lub równa n (getLargestPrime(int number)). Tablica boolowska jest zaszyta w standardowym obiekcie BitSet. To najprostsza implementacja, której jedyną optymalizacją jest liczenie sita od wartości ostatniego liczenia. Reszta informacji w komentarzach.
Cała implementacja jest w metodzie void przeliczSito(final int number). Ledwo 80 wierszy kodu.

0

teraz już zaczynam rozumieć powoli kod, ale jeśli mam do stworzenia konstruktor który tworzy tablice boolowska to czy mogę użyć gotowej struktury z obiektu BitSet?

0

Należy wtedy w samym konstruktorze (na jego końcu) wrzucić wywołanie przeliczSito(n), gdzie n jest parametrem konstruktora, wtedy późniejsze wywołania isPrime oraz getLargestPrime sprowadzą się jedynie do wyszukania odpowiedniego bita w tablicy BitSet (chyba, że później żądana liczba przekroczy tą podaną w konstruktorze - wtedy będzie jeszcze trochę obliczeń).
Nie wrzuciłem tego tam ponieważ tak powoli działający konstruktor stwarza bardzo długi stan zawieszenia między wywołaniem new, a stworzeniem obiektu. Wtedy nie wiadomo czy długi czas oczekiwania na obiekt jest spowodowany problemem braku pamięci na obiekt, czy obliczeniami. W efekcie łączny czas wywołania konstruktora oraz jednej z metod isPrime lub getLargestPrime nie zmieni się, ale ogromna większość zużytego czasu przeniesie się do konstruktora.

Jednak najczęściej lepiej jest aby długotrwałe obliczenia były tam gdzie wszyscy się tego spodziewają, czyli wywołaniu metody sprawdzającej czy liczba jest pierwsza lub wyszukującej największą liczbę pierwszą ograniczoną od góry. Wtedy konstruktor zajmuje się tylko utworzeniem obiektu, a metody właściwymi obliczeniami i uzyskaniem wyniku.

0

a możesz wrzucić przykładowy taki kod?

0

Przecież opisałem wszystko. Prościej chyba się nie da.

        public FreePrimes(final int maxNumber)
        {
                this.podzielna = new BitSet(maxNumber);
                init();
                przeliczSito(maxNumber);
        }

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0