nie mogę zrozumieć dlaczego mój kod nie wypisuje poprawnej wartości dla np przedziału od 12 do 50

Question

#include <iostream>

using namespace std;


bool czy_pierwsza(int n)
{
    if(n<2)
        return false; //gdy liczba jest mniejsza niż 2 to nie jest pierwszą

    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false; //gdy znajdziemy dzielnik, to dana liczba nie jest pierwsza
    return true;
}
int main()
{
  int n,x,y,w=0;
  cin>>n;
  while(n--)
  {
      cin>> x>>y;
      for(int i=x;i<=y;i++)
      {
          if(czy_pierwsza(i))
            w+=1;

      }

  } cout<<w<<endl;

    return 0;
}

Witam, nie wiem dlaczego dla niektorych przedzialów wypisuje mi złe wartości a np dla przedziału od 6 do 19 dobre. link do probmelu---> https://pl.spoj.com/problems/DYZIO2/

Answer 1

Nie czyścisz zmiennej w, po / przed zapytaniem

Żeby zrobić to szybciej niz O(N * (Y-Z) * SQRT(Y)) Musisz użyć sita Eratostenesa. I wtedy dostaniesz O(N*(Y-X))

Comments

Aaaaaa nie sorki, co do tego przyśpieszenia z sitem Eratostenesa

Sitem naliczysz wszystkie liczby pierwsze do maksymalnej wartosci Y jaka masz w zadaniu chyba w treści pisze 10^6, i naliczysz sumy prefiksowe (albo drzewo przedziałowe punkt-przedział, ale to bez sensu bo będzie trudniej w implementacji i jeszcze loga dostaniesz w złożonności, czyli słaby interes) i na zapytania odpowiesz w czasie stałym. O(1), O(N + 10^6), koszt odpalenia sita, lub jesli napiszesz drzewko przedziałowe punkt-przedział to O(N * lg 10^6 + 10^6).

---

Już rozumiem o co chodzi z tym czyszczeniem, dzięki wielkie za pomoc