Na szkoleniu trener zadał nam zadanie, aby napisać metodę, która znajdzie liczby pierwsze z danego zakresu liczb.
Czy jest w języku Java jakaś funkcja do tego? Może w jakiejś bibliotece typu Guava?
-
4
-
5
-
287
Odpowiedzi (4)
Zaloguj się, aby móc oceniać, komentować, odpowiadać...
-
1
Naprawdę trzeba to pisać tak:
for (int i = 1; i < 300; i++) {
int podzielnik = 2;
boolean liczbaPierwsza = true;
if (i > 3) {
while (podzielnik < i) {
if (i % podzielnik == 0) {
liczbaPierwsza = false;break;
}
podzielnik++;}
}
if (liczbaPierwsza) {
System.out.println("Liczba pierwsza: " + i);
}
}
-
16
Witam,
rzeczywiście tworzenie rozwiązania w ten sposób jest męczące, jednak jak to bywa w JAVA, większość takich standardowych problemów została już rozwiązana. :-) Możemy skorzystać z biblioteki Apache Commons -> Primes
Dysponuje on metodami
- Primes.isPrime(int n) - która zwraca informację, czy liczba jest liczbą pierwszą
- Primes.nextPrime(int n) - zwraca następną liczbę pierwszą
- Primes.primeFactors(int n) - zwraca listę wszystkich liczb pierwszych dla podanego zakresu
Pozdrawiam
Komentarze
na pewno sie przyda - dzieki :-)
Skomentował
:
@
,08.02.2015
-
2
-
1
-
4
-
1
A właśnie znalazłem, że klasa BigInteger ma metodę isProbablePrime(int), więc nie trzeba używać zewnętrznych bibliotek.
-
11
Jeżeli zdecydujemy się na własną implementację algorytmu wyszukiwania liczb pierwszych, to można go zapisać bardziej optymalnie, o ile zauważymy, że jeżeli liczba N posiada podzielnik p (1<p<N), to także posiada drugi podzielnik N/p.
Wtedy weryfikację, czy liczba N jest pierwsza można przerwać, gdy znajdziemy mniejszy z tych dwóch podzielników, a to oznacza warunek:
Wtedy algorytm poszukiwania liczb pierwszych można zapisać następująco:
next:
for (int liczba = 2; liczba < N; liczba++) {
for (int podz = 2, limit = (int)Math.sqrt(liczba); podz <= limit; podz++) {
if (liczba % podz == 0) {
continue next;
}
}
System.out.println("Liczba pierwsza: " + liczba);
}
W porównaniu do wcześniej przedstawionego algorytmu, ten ma mniejszą złożoność obliczeniową.
