Witam.
Czy ten algorytm jest poprawny pod względem wydajnościowym? (Wiem nie obsługuje liczb ujemnych)
public boolean czyPierwsza(int liczba){
for (int i = 2; i < liczba; i++) {
if (liczba%i==0) {
return false;
}
}
return true;
}
Witam.
Czy ten algorytm jest poprawny pod względem wydajnościowym? (Wiem nie obsługuje liczb ujemnych)
public boolean czyPierwsza(int liczba){
for (int i = 2; i < liczba; i++) {
if (liczba%i==0) {
return false;
}
}
return true;
}
Nie.
możesz poprawić wydajność w sposób kwadratowy.
W linku znajduje się opis użycia pierwiastka.
http://edu.i-lo.tarnow.pl/inf/utils/010_2010/0209.php
Co do wydajnego algorytmu, to szukaj pod Sito Eratostenesa. Chodzi generalnie o to żeby sprawdzać resztę z dzielenia tylko przez liczby pierwsze mniejsze lub równe pierwiastkowi szukanej (jak coś dzieli się przez wielokrotność danej liczby to przez tą liczbę też). Co prawda trzeba będzie sprawdzić też liczby mniejsze od szukanej, ale w rezultacie końcowym opłaci się.
Ogólnie jeszcze wydajniej jest sprawdzać czy liczba N jest podzielna przez liczby PIERWSZE mniejsze lub równe pierwiastkowi liczby N. Trzeba zrobić listę, wrzucić na nią "2", a potem lista sama się będzie budowała. Minus taki, ze jest problem z wyszukiwaniem liczb jeśli nie zaczynamy od 1, tylko np od 100000.
Przed rozważaniami o wydajności, trzeba ustalić jaki jest problem: