C++ Algorytm wybierający liczby pierwsze

Question

Witam

Zadanie na SPOJ'u - liczby pierwsze. Na dole moja nieudolna próba napisania sita Eratostenesa.

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int X,P,D,R,A,S,L;
    L=1;
    cin >> X;
    for(int i=1; i<=X; i++)
    {
        cin >> P >> D;
        int jd[D];
        S=pow(D,1/2);

            for(int j=P; j<=S; j++)
            {
                R=pow(j,2);
                int P=R;
                while(R<=D)
                {
                    jd[j]=true;
                    jd[R]=false;
                    cout<<jd[j]<<" ";
                    R=P+(L*i);
                    L++;
                }
            }
    }


    return 0;
}

Zdaję sobie sprawę, iż nie uwzględniłem że liczba  1 nie jest liczbą pierwszą. W konsoli wyskakuje mi (Przy podaniu cyfr 1 i 10) 0 1 1 1 1 1 1 1 1 1. << KOmpletnie nie wiem czemu, męczę się z tym trochę czasu. Mógłby mnie ktoś naprowadzić? A, wiem że ten kod na pewno idzie napisać lepiej (krócej, efektywniej) ale ja się dopiero uczę, chciałby żeby ten Frankenstein działał a póżniej go zoptymalizować :P

Answer 1

Sporo kombinowałeś, może napiszę swoje sito:

int N = 100;
vector<bool> czyZlozona(N);
for(int i = 2; i*i<N; i++)
{
    if(czyZlozona[i] == false)
    {
       for(int j = i*i; j<N; j+=i)
       {
              czyZlozona[j] = true;
       }
    }
}

fo(int i = 2; i<N; i++)
{
   if(czyZlozona[i] == false)
      cout << i << " ";
}

 

 

Comments

Przecież vector czyZlozona ma niezdefiniowany stan początkowy, a ty na takich danych pracujesz, sprawdzając, czy są równe false. Gdzie tu sens?

---

Oj...

#include <vector>
#include <iostream>

struct C {
    C() {
        std::cout << "Konstruktor C.\n";
    }
};

int main() {
    std::vector<C> vec(10);
}

I jeszcze pytanie jaki wynik ma domyślny konstruktor dla typu bool ?

---

Typy wbudowane nie mają konstruktorów. Jeśli nie przypiszesz nic do zmiennych bool, to będą miały one po prostu śmieci.

---

vector jest na tyle mądry że sobie to zeruje

---

@Patrycjerz Nie masz racji. Konstruowanie std::vector także dla typów POD powoduje uruchomienie ich konstruktorów i "czyszczenie pamięci" (np dla int zawsze będzie tam 0), dla bool będzie tam false. Mówi o tym wyraźnie standard języka jeszcze przed czasami C++11. Oczywiście mówię o kontenerach napisanych jako klasy a nie pasywnej tablicy znanej z C. Ona nic nie inicjuje. 

Może przykład będzie deskryptywny. Z premedytacją alokuję std::vector<int> i wypełniam go wartościami. Po wyjściu z zakresu kontener jest niszczony. Robię go jeszcze raz ale dla typu bool. Za każdym razem będzie tam false (w przykładzie zakładam że będzie to ta sama przestrzeń pamięciowa żeby nie komplikować).

#include <iostream>
#include <vector>

int main() {
    {
        std::vector<int> vec(50, 999);
    }
    {
        std::vector<bool> vec(50);
        for(const auto& b: vec) {
            std::cout << std::boolalpha << b << ' ';
        }
        std::cout << '\n';
    }

    // Konstruktor typu int... jednak go ma
    int w{};
    // Konstruktor dla bool... jednak go ma
    bool check{};
    std::cout << "check = " << std::boolalpha << check << std::endl;
    std::cout << "w = " << w << std::endl;
}

 

---

Mówiąc, że typy wbudowane nie mają konstruktorów, kierowałem się odpowiedziami stąd. A co do braku zerowania pamięci wektora przy użyciu konstruktora z ilością elementów, kierowałem się tym. Okazało się jednak, że konstruktor numerowany dwójką ma dwie wersje, do C++11 i od C++11, więc przed tym standardem podanie jedynie ilości elementów powoduje nadanie wartości w postaci T(), co dla typu wbudowanego byłoby wartością niezdefiniowaną, ale od C++11 wywoływany jest wtedy konstruktor trzeci, który już zeruje (notka na dole strony).

Wynika więc z tego, że mogłem nieco lepiej przeczytać dokumentację.

---

Nie. T() dla int to 0 i zawsze tak było inicjowane. To kwestia zdefiniowanej składni dla POD'ów. C++11 tu nie wprowadza zmiany. Przeczytaj pkt 2 z uwagą. Nie masz racji ale nie będę Cię więcej przekonywał. EOT.

---

Ale gdzie mam przeczytać ten punkt? Racja, T() zwraca zero, zarówno w GCC, jak i w VSC++. Nie wiedziałem o takiej właściwości tego zapisu, zaskoczyłeś mnie tym.

---

W dokumentacji którą zacytowałeś: http://en.cppreference.com/w/cpp/container/vector/vector

2) Constructs the container with count copies of elements with value value.

---

Ale ja dobrze rozumiem konstruktor z punktu 2. Jedynym nierozumieniem był zapis T() i jego generowanie zera zamiast wartości niezdefiniowanej.

---

Spoko.. wyjaśnione :-)

---

No i dziękuję za wyjaśnienie mojej niewiedzy