pomoc ze zrozumieniem kodu (liczby pierwsze)

pytanie zadane 26 maja 2016 w C i C++ przez Ziwer Nowicjusz (200 p.)
edycja 14 sierpnia 2016 przez Patrycjerz

Witam, ostatnio zainteresowałem się napisaniem programu na wypisywanie wszystkich liczb pierwszych z przedziału [n ; 100]. Szukałem w internecie wielu gotowych kodów aby na ich podstawie spróbować samemu napisać coś podobnego. Nie za bardzo rozumiem logicznie działania tego kodu. Bardzo proszę o pomoc ! Dzięki :)

#include <iostream>
#include <cmath>
using namespace std;
int main ()

{

    cout<<"Liczby pierwsze z przedzialu: "<<endl;
    for (int i=10;i<=100;i++)
    {
        if (i==2)cout<<i;

        for (int j=2;j<=ceil(sqrt(i));j++)
        {
            if ((i%j)==0)
            break;

            if (j==ceil(sqrt(i)))
            cout<<i<<" ";
        }
    }


    return 0;
}

komentarz 15 sierpnia 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Jak już cię interesuja liczby pierwsze, to zobacz sobie o algorytmie sita erastotenesa. Algorytm prosty, fajny i wydajny :)

komentarz 15 sierpnia 2016 przez manjaro Nałogowiec (37,390 p.)

Jak już to Eratostenesa ;D

Jest to chyba najbardziej optymalny algorytm. W przedziale 0-1000000 liczb znajduje liczby pierwsze w 0.00s wg spoja.

Tutaj masz schemat https://pl.wikipedia.org/wiki/Sito_Eratostenesa a kod sobie zaimplementuj.

komentarz 15 sierpnia 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Niestety nie jest to optymalny generator liczb pierwszych. Jest trochę wydajniejszy algorytm i jest to sito atkina bensa czy jakoś tak

2 odpowiedzi

odpowiedź 26 maja 2016 przez bartolinciu Dyskutant (7,580 p.)

#include <iostream>
#include <cmath>
using namespace std;
int main ()

{

    cout<<"Liczby pierwsze z przedzialu: "<<endl;
    for (int i=10;i<=100;i++)//"przechodzi" po liczbach 10-100
    {
        if (i==2)cout<<i;//jeśli zmienna i wynosi 2 wypisuje ją, nigdy się nie sprawdzi

        for (int j=2;j<=ceil(sqrt(i));j++)//"przechodzi" po liczbach 2 - zaokrąglenie w górę pierwiastka kwadratowego z i
        {
            if ((i%j)==0)//przerywa pętlę jeśli reszta z dzielenia i/j jest równa 0
            break;

            if (j==ceil(sqrt(i)))//jeśli zmienna j jest równa zaokrąglonemu w górę pierwiaskowi kwadratowego z i
            cout<<i<<" ";
        }
    }


    return 0;
}

odpowiedź 14 sierpnia 2016 przez Sinnley Stary wyjadacz (12,810 p.)

Kod, który pokazałeś sprawdza, czy liczba z głównej pętli, która "przechodzi" po przedziale ma jakikolwiek dzielnik.

Jeśli więc szukasz liczb pierwszych z przedziału [n ; 100] potrzebna ci główna pętla for, która aż do 100 będzie zwiększała początkową wartość czyli liczbe z lewej strony przedziału. Musisz też pamiętać, że n musi wynosić conajmniej 2, bo 1 nie jest uznawane za liczbę pierwszą.

Wewnątrz pętli głównej masz pętle poboczną odpowiadającą za sprawdzanie czy liczba ma jakiś dzielnik.Sprawdza to za pomocą operatora "%" zwracającego reszte z dzielenia. Jeśli reszta wynosi 0 to znaczy, że liczba ma dzielnik i nie jest pierwsza.

Algorytm, który podałeś jest tym najbardziej optymalnym. Jak łatwo zauważyć pętla poboczna nie sprawdza wszystkich "teorytycznie możliwych" dzielników, a jedynie te mniejsze, bądź równe pierwiastkowi sprawdzanej liczby. Wynika to z tego, że jeśli liczba ma dzieliniki większe od 1, to będzie ich tyle samo po lewej stronie i prawej stronie od tego pierwiastka. NP:

Pierwsatek z 36 wynosi 6.

36 - dzielniki to 2, 3, 4, 6, 12, 18, 36