• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

pomoc ze zrozumieniem kodu (liczby pierwsze)

VPS Starter Arubacloud
0 głosów
403 wizyt
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,910 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,910 p.)
Niestety nie jest to optymalny generator liczb pierwszych. Jest trochę wydajniejszy algorytm i jest to sito atkina bensa czy jakoś tak

2 odpowiedzi

+2 głosów
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;
}

 

+1 głos
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

 

Podobne pytania

0 głosów
1 odpowiedź 437 wizyt
pytanie zadane 30 marca 2017 w C i C++ przez WireNess Stary wyjadacz (11,240 p.)
0 głosów
1 odpowiedź 781 wizyt
pytanie zadane 10 kwietnia 2016 w C i C++ przez danior Początkujący (330 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...