Program spisujący liczby pierwsze

Question

Cześć

Mam taki problem, ponieważ zaczynam swoją przygodę z Java ale niestety średnio mi to idzie i nie rozumiem działania jednej pętli w programie wyszukującym liczby pierwsze w przedziale 2-100. Mianowicie chodzi o zagnieżdżoną pętle- nie rozumiem tego if z modulo, bo jeżeli i % j ==0, a każda pętla zaczyna się od tej samej wartość, tj. i=2, j=2 to przecież w każdym przypadku będzie isprime = false. Moglibyście mi to wytłumaczyć gdzie popełniam błąd w mysleniu?

W dodatku nie rozumiem warunku j <= i / j, dlaczego taki ma miejsce?

public class Test {
    //Napisz program wyszykujący wszystkie liczby pierwsze z przedziału 2 - 100
    public static void main(String[] args) {

        int i, j;
        boolean isprime;

        for (i = 2; i <= 100; i++){
            isprime = true;

           for (j = 2; j <= i / j; j++)
                if ((i % j) == 0) isprime = false;
            if (isprime)
                System.out.println(i + " jest liczbą pierwszą");

Z góry dzięki za pomoc i pozdrawiam

Comments

No nie, tylko na starcie zaczyna się od 2,2, potem już jest 3,2 itp. Zewnątrzna pętla to po prostu wyliczenie wszystkich liczb w zadanym przedziale, wewnętrzna pętla sprawdza czy dana liczba jest pierwsza poprzez sprawdzenie przez co się dzieli całkowicie.

Faktem jest, że ta druga pętla jest mocno nieoptymalna i trochę dziwnie wygląda ten warunek kontynuacji (j < i/j). Jeśli chodziło ci o warunek podobny do j < sqrt(i), czy nie prościej i czytelniej zapisac (j*j < i). Jednak ten warunek należy zapisać jako nieostry (<=), bo przecież są liczby które są kwadratami innych liczb pierwszych.

Jeśli program już ustali, że dana liczba nie jest pierwsza, nie ma sensu dalsze jej sprawdzanie. Czyli jak podstawiasz false pod is_prime to od razu break.

Tak dla jasności - do wyszukania wszystkich liczb pierwszych w danym zakresie najlepszy jest algorytm sita Erastotenesa.