Wyliczanie liczba pierwszych - Java


(marcinkk) #1

Witam, napisałem program który ma wypisywać liczby które nie są liczbami pierwszymi. Gdy w drugiej pętli for: j <= i, wtedy dostaje błędne wyniki.

run:

liczba 3 nie jest liczba pierwsza

liczba 4 nie jest liczba pierwsza

liczba 6 nie jest liczba pierwsza

liczba 8 nie jest liczba pierwsza

liczba 9 nie jest liczba pierwsza

liczba 10 nie jest liczba pierwsza

liczba 12 nie jest liczba pierwsza

liczba 14 nie jest liczba pierwsza

liczba 15 nie jest liczba pierwsza

liczba 16 nie jest liczba pierwsza

liczba 18 nie jest liczba pierwsza

liczba 20 nie jest liczba pierwsza

BUILD SUCCESSFUL (total time: 0 seconds)

Liczby 2 nie wypisało i wypisało że liczba 3 nie jest liczba pierwsza. Natomiast gdy: j < i program działa dobrze z założeniem, wypisuje wszystkie liczby które nie są pierwsze do n.

/*

 * To change this template, choose Tools | Templates

 * and open the template in the editor.

 */

package javaliczbypierwsze;


/**

 *

 * @author marcin

 * program wypisuje liczby ktore nie sa pierwsze

 */

public class JavaLiczbyPierwsze {


    /**

     * @param args the command line arguments

     */

    public static void main(String[] args) {

        int licznik = 0;

        int n = 20;

        for (int i = 2; i <= n; ++i) {

            for (int j = 1; j < i; ++j) {

                if (i % j == 0) {

                    licznik++;

                }

                if (licznik > 2) {

                    System.out.println("liczba " + i + " nie jest liczba pierwsza");

                    licznik = 0;

                    break;

                }

            }

        }

    }

}

run:

liczba 4 nie jest liczba pierwsza

liczba 6 nie jest liczba pierwsza

liczba 8 nie jest liczba pierwsza

liczba 10 nie jest liczba pierwsza

liczba 12 nie jest liczba pierwsza

liczba 14 nie jest liczba pierwsza

liczba 15 nie jest liczba pierwsza

liczba 16 nie jest liczba pierwsza

liczba 18 nie jest liczba pierwsza

liczba 20 nie jest liczba pierwsza

BUILD SUCCESSFUL (total time: 0 seconds)


(Razi) #2

Nie zerujesz licznika w przypadku gdy ten warunek tam nie będzie spełniony, licznik=0 wstaw na początek pierwszej pętli (dalej jest zbędny). No i powinno być j<=i przy takim szukaniu.

Optymalnie byłoby j=2 ; j<=Math.sqrt(i); j++. Tyle że ten pierwiastek wyznaczasz przed pętlą.


(marcinkk) #3

masz rację zadziałało, możesz napisać czemu nie działało?? chodzi o zasięg zmiennej??


(Drobok) #4

o to, że masz go w if (zerujesz tylko jak warunek się spełni :P)


(marcinkk) #5

teraz dobrze działa.

/*

 * To change this template, choose Tools | Templates

 * and open the template in the editor.

 */

package javaliczbypierwsze;


/**

 *

 * @author marcin

 * program wypisuje liczby ktore nie sa pierwsze

 */

public class JavaLiczbyPierwsze {


    /**

     * @param args the command line arguments

     */

    public static void main(String[] args) {

        int licznik;

        int n = 20;

        for (int i = 2; i <= n; ++i) {

            licznik = 0;

            for (int j = 1; j <= i; ++j) {

                if (i % j == 0) {

                    licznik++;

                }

                if (licznik > 2) {

                    System.out.println("liczba " + i + " nie jest liczba pierwsza");

                    licznik = 0;

                    break;

                }

            }

        }

    }

}

(Drobok) #6

teraz zerujesz licznik na początku pętli, oraz wtedy kiedy warunek jest spełniony :stuck_out_tongue:


(marcinkk) #7

możesz więc poprawić


(kostek135) #8

Twój algorytm jest … emmm … beznadziejny, trudno znaleźć inne słowo.

Po pierwsze: Każda liczba jest podzielna przez 1 i samą siebie, więc na dobrą sprawę wystarczy jeden if przy zmienionym zakresie pętli. Niby nic, ale dla liczb posiadających rozkład 2*p przeglądasz połowę zakresu.

Przykład masz liczbę 2026, czyli 2 * 1013 - obie są pierwsze, twój algorytm stwierdzi, że jest ona złożona w momencie dotarcia do liczby 1013, czemu nie przy znalezieniu 2?

Po drugie: Każda liczba a jest podzielna przez b jeśli istnieje c takie ze b * c = a, a stąd w oczywisty sposób wynika, że nie ma sensu sprawdzać liczb większych od pierwiastka kwadratowego z danej liczby, bo jeśli da się przeprowadzić faktoryzację to jej mniejszy czynnik może wynosić co najwyżej pierwiastek kwadratowy z tej liczby. Jeśli tego nie rozumiesz, przeprowadź dowód nie wprost korzystając z rozdzielności mnożenia względem dodawania.

Po trzecie: Sita są wydajniejsze do szukania wielu liczb (Eratostenesa, liniowe).


(Graczek13) #9

Jak można przekształcić ten kod z 5 posta aby program wypisywał TYLKO liczby pierwsze?