Liczby pierwsze - java

Odpowiedz Nowy wątek
2011-10-07 13:21
0

Mam za zadanie napisanie programu, który dla podanych liczb naturalnych wypisze je w kolejnych liniach z informacją czy jest to liczba pierwsza, czy nie.

Coś napisałem, proszę o sprawdzenie kodu pod względem wydajności, funkcjonalności, być może można coś dodać, przerobić

public class pierwsze 
        {        
                public static boolean prime(int n) 
                { 
                        if (n>2) 
                        { 
                        double sq = Math.sqrt(n); 
                        if(n%2==0) 
                        return false; 
                                else 
                                { 
                                for(int i=3; i<=sq; i+=2) 
                                        { 
                                                if(n%i==0) 
                                                { 
                                                return false; 
                                                } 
                                        } 
                                        return true; 
                                                } 
                                                } 
                else if (n==2) return true; 
                return false; 
                                } 

        public static void main(String args[]) 
        { 
        int n=0; 
        for(int i=0; i<args.length; i++) 
        { 
                try 
                { 
                        n=Integer.parseInt(args[i]); 
                        if (prime(n)) System.out.println(n + " jest liczba pierwsza"); 
                        else System.out.println(n + " nie jest liczba pierwsza"); 
                                } 
                                catch (NumberFormatException ex) 
                                { 
                                System.out.println(args[i] + " nie jest liczba calkowita"); 
                                }                      
                        } 
        } 
} 

Pozostało 580 znaków

2011-10-07 13:28
bo
0

Wygląda nieźle. Widzę dwie usterki:

  • co z liczbami ujemnymi
  • komunikat typu "222222222222222222222222222222222 nie jest liczba całkowitą" będzie wyglądał dziwnie.

Pozostało 580 znaków

2011-10-07 13:59
0

Dla liczb ujemnych będzie wyświetlał się komunikat, że taka liczba nie jest liczbą pierwszą, natomiast dla ogromnych liczb .... coś tutaj należy zmienić, chyba, że dla takich liczb zakres zostaje przekroczony.

Pozostało 580 znaków

2011-10-07 14:44
0
  • popraw formatowanie kodu (klamry, wcięcia)
  • nazwa klasy z reguły rozpoczyna się wielką literą
  • nazwa metody, zgodnie z konwencjami, powinna być "isPrime(int n)" -> bo zwraca boolean
  • komunikat dla wyjątku zmień na "nie jest poprawną liczbą typu integer"
No nie wiem czy się powinno tutaj konwencje rozpatrywać, szczególnie poprzedzanie funkcji zwracających bool is. Ja np. wolę wersję if(number.prime()), niż if(number.isPrime()). Szczególnie to by było mylące tutaj, bo prime() nie jest za bardzo metodą. Co do klas to się zgadzam, dorzuciłbym do tego FunkcjeStatyczne, ale to moje widzimisie. - Zjarek 2011-10-09 01:20
Ja bym w ogóle nie zgodził się na robienie tej funkcji statyczną. Tak, jak niżej jest napisane - dla sita Erastotenesa można by było trzymać wyniki już obliczone -> zatem jakiś obiekt by się przydał (tak, wiem, że w kolekcji będącej polem statycznym też dałoby radę). A poza tym - nie miesza się nazw polskich ("pierwsze") z angielskimi ("prime") (do to autora tematu). A co do konwencji... ja jednak lubię się ich trzymać ;) - [losowa nazwa] 2011-10-09 01:25

Pozostało 580 znaków

2011-10-08 13:54
0

Prócz tego coś jeszcze należałoby zmienić?
czy sposób znajdywania liczb pierwszych jest poprawny?

Pozostało 580 znaków

2011-10-08 16:49
0
if(n<2) return false;
if(n%2==0) return n==2;
if(n%3==0) return n==3;
//if(n<25) return true;
for(i=5; i<=sq ; n=n+6){  // omijamy także krotności 3
    if(n%i==0) return false;
    if(n%(i+2)==0) return false;}
edytowany 2x, ostatnio: Xitami, 2011-10-08 16:52

Pozostało 580 znaków

2011-10-08 17:09
0

LooooooooooooooooooooooooooooooooooooooooooooooooooooooooooL
http://pl.wikipedia.org/wiki/Sito_Eratostenesa i masz tam nawet implementację w Javie.


Pokaż pozostałe 2 komentarze
a właśnie, gdzie postawić granicę? wszystko mieści się w maszynowym słowie, Eratostenes bez udziwnień, maszyna bez pamięci podręcznej - Xitami 2011-10-08 18:35
@bogdans bardzo duże. Generujesz raz i sprawdzenie pierwszości masz w O(1). - hauleth 2011-10-08 18:36
konkurentem oczywiście "trial factoring" - Xitami 2011-10-08 18:37
@winerfresh, z kodu wynika, że program jest uruchamiany tak: java pierwsze liczba1 liczba2 ... Sito miałoby pewien sens tylko wtedy gdyby program sprawdzał na starcie istnienie pliku z liczbami pierwszymi z zakresu [2,2<sup>31</sup>-1]. W przypadku braku tworzyłby ten plik, w przeciwnym razie odczytywał cały (tylko odpowiednio duży fragment) tego pliku. W zdecydowanej większości przypadków działanie byłoby wolniejsze niż wywołanie kilka razy dobrze napisanej funkcji isPrime(..). A Ta jest dobrze napisana. - bogdans 2011-10-08 19:54
Ja bym wygenerował używając sita wszystkie 16 bitowe liczby pierwsze, gdy spodziewane są 32 bitowe. Dzięki temu można w miarę szybko sprawdzić czy dana liczba jest pierwsza przy małym narzucie pamięciowym. - Zjarek 2011-10-09 01:23

Pozostało 580 znaków

2011-10-08 23:17
0

ale sitem Eratostenesa raczej nie za bardzo będę w stanie wpisać odpowiednie liczby i wiedzieć, czy jest pierwsza, czy nie?

Pozostało 580 znaków

2011-10-09 10:40
0

Jak to nie? Dostajesz zbiór liczb, wybierasz z nich największą i do jej wartości liczysz sito. Na koniec już tylko sprawdzasz czy jakaś liczba ze zbioru wejściowego została odsiana (jako pierwsza) czy skreślona.


Jeżeli ktoś komuś coś, ewentualnie nikt nikomu nic, to właściwie po co...?

Pozostało 580 znaków

2011-10-09 11:49
bo
0

Wybór, sito czy funkcja isPrime() powinien zależeć od ilości liczb, których "pierwszość" chcemy zbadać. Jeżeli n=15 485 857 (liczba jest pierwsza, i jest typu int), to czas wykonania funkcji isPrime(n) wynosi 0.2 ms., a czas stworzenia sita wynosi około 500 ms. Celowo wybrałem liczbę pierwszą, by sprawdzanie trwało długo. Ponieważ program uruchamiamy tak java pierwsze liczba1 liczba2 ..., to jest mało prawdopodobne by ilość liczb była duża. Uważam zatem użycia sita za nieuzasadnione.

na czuja wydaje mnie mi się, że jeśli takie sito zajęło pół sekundy, to nie jest dobrze napisane. Czyli da się chyba poprawić proporcje na korzyść sita, ale... Co do zasadniczych spraw to zgadzamy się w 100% - Xitami 2011-10-09 16:51
Sito Eratostenesa jest najszybszą znaną metodą wyszukiwania liczb pierwszych w ograniczonym zbiorze. Jedyną operacją jest w nim tylko dodawanie. Algorytm z metody powyżej jest jednym z najwolniejszych sposobów ponieważ występują masowe dzielenia i żadne informacje pośrednie nie są zapamiętywane. Nawet na szybkim CPU wykonanie dodawania całkowitego jest szybsze od reszty z dzielenia zmiennoprzecinkowego. Łatwo się o tym przekonać dla największej znanej 32-bitowej liczby pierwszej czyli Integer.MAX_VALUE. W Javie łatwo wykonać dobrą implementację sita używając klasy BitSet. - Olamagato 2011-10-09 19:15

Pozostało 580 znaków

2011-10-09 20:53
0

a tak w ogóle czy ten kod, który podałem wyżej jest poprawny, bo Xitami napisał, że coś tam mogę dodać, ale czy tak nie może zostać, chodzi mi o sa.m kod , który dla podanych konkretnych liczb wypisuje czy jest to liczba pierwsza.

Sito Eratostenesa mogę użyć, mam nawet gotowy kod na wikipedii, ale mógłby ktoś podrzucić jakiś pomysł, w jaki sposób zmienić ten kod bym mógł wypisywać liczby i sprawdzać, jaka to liczba?
czy może wystarczy lekko podrasować kod który mam i będzie dobrze?

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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