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

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