Algorytm strawdzający czy liczba jest liczbą pierwszą

0

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;
}
0

Nie.

1

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

2) nie musisz sprawdzać liczb parzystych większych od 2

1

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ę.

1

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.

1

Przed rozważaniami o wydajności, trzeba ustalić jaki jest problem:

  • znaleźć liczby pierwsze <= n,
  • znaleźć liczby pierwsze z przedziału [k,n],
  • rozstrzygnąć czy dana liczba n jest pierwsza.

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