[Algorytmy] Ile jest liczb pierwszych na przedziale

[mario765i]

Witam. Jest to mój pierwszy post na tym forum. Niedawno zacząłem przygodę z programowaniem w c++. Mam do napisania program, w którym należy podać z klawiatury liczbę testowanych przedziałów, następnie wprowadzić granicę tych przedziałów i na wyjściu ma być ilość liczb pierwszych na każdym z podanych przedziałów. Napisany przeze mnie program wyświetla poprawnie tylko ilość liczb pierwszych na ostatnim z podanych przedziałów, z kolei na wcześniejszych przedziałach wyświetla ilość liczb pierwszych z ostatniego przedziału. Proszę o pomoc w zmodyfikowaniu tego kodu, piszę w CodeBlocks.

Kod: Zaznacz cały

#include<iostream>
#include<string>
using namespace std;

/*
 * Sito Eratostenesa
 * Generowanie liczb pierwszych z przedzia³u [2 , SIZE]
 */

const int b = 1000000;
bool A[b+1];  // A[k] = "czy k jest liczb¹ z³o¿on¹?"
void sitoEratostenesa()
{
	int n, p;
	// myœlimy, ¿e wszystkie liczby s¹ pierwsze
	for (n=2; n<=b; n++)
	{
		A[n] = false;
	}

	for (p=2; p*p<=b; p++)
	{
		if (A[p]==false) // p jest liczb¹ pierwsz¹
		{
			// wykreœlamy wielokrotnoœci liczby p
			// zaczynamy od wielokrotnoœci p^2
			for (n=p*p; n<=b; n=n+p)
			{
				A[n] = true;
			}
		}
	}
	// Teraz tablica A mówi nam które liczby s¹ pierwsze
	// Mianowicie
	//  p jest l. pierwsz¹  <=>  A[p]==false
}

// Funkcja sprawdza, czy p jest liczb¹ pierwsz¹
// Czas dzia³ania: O(1)
bool isPrime(int p)
{
	if (A[p]==true) return false;
	return true;
}


// Program oblicza ile jest liczb pierwszych w przedziale [2, SIZE]
int main()
{
	int licznik, p;
	sitoEratostenesa();
	int a,b;
	//cin >> a >> b;
	int N;
	cin >> N;
	int tab[N];
	int i=0;
	for(i=0; i<N; i++)
	{
	    cin >> a >> b;
	}
for(i=0; i<N; i++){
	licznik = 0;
	for (p=a; p<=b; p++){
		if ( isPrime(p) ){
			licznik++;}}
	cout << licznik << "
";}
	return 0;
}

[adambak]

ogólnie to ładnie tylko logika coś Ci siada.. bo jeśli

Kod: Zaznacz cały

 
if (A[p]==true) return false;

to tak śmiesznie, ale może się czepiam

kod po poprawkach:

Kod: Zaznacz cały

#include<iostream>
#include<string>

using namespace std;

const int b = 1000000;
bool A[b+1];

void sitoEratostenesa()
{
  int n,p;

  for (n=2; n<=b; n++)
    A[n] = false;

  for (p=2; p*p<=b; p++)
  {
    if (A[p]==false)
      for (n=p*p; n<=b; n=n+p)
        A[n] = true;
  }
}


bool isPrime(int p)
{
  if (A[p]==true) return false;
  return true;
}

int main()
{
  int licznik, p;
  sitoEratostenesa();
  int a,b;
  int N;
  cin >> N;
  int tab[N];
  int i=0;

  for(i=0; i<N; i++){
    cin >> a >> b;

    licznik = 0;
    for (p=a; p<=b; p++){
      if ( isPrime(p) )
        licznik++;
    }

    cout << licznik << "
";
  }
  return 0;
}

błąd był mały w funkcji main.. otóż.. a co ja tam będę gadał, sam zobacz, wiele nie zmieniłem, po prostu ustawienie klamerek.. główną pętlę źle wykonywałeś bo najpierw pobierałeś a i b w pętli.. a potem w osobnej działałeś na tych a i b.. no to nie ma szans, żeby pamiętał tamte wartości.. musisz to sprawdzanie zrobić w forze, który będzie zagnieżdżony w tym pierwszym..

poza tym sprawdź co Ci wypisze dla:

Kod: Zaznacz cały

1
0 1

Twój program wypisze:

Kod: Zaznacz cały

2

czyli traktuje te dwie liczby nie tak jak się matematycy umówili


a na koniec taka drobna "ciekawostka": deklarując globalną tablicę w większości przypadków (w tym w CodeBlocks też) wypełniasz ją samymi zerami.. czyli tak jest i tutaj.. a zero odpowiada wartości logicznej false.. dlatego pierwsza pętla w sicie jest niepotrzebna, sprawdź i się przekonaj.. jednak na Twoim miejscu bym poprawił ten logiczny aspekt o którym wspomniałem na początku postu i z takich sztuczek nie korzystał.. przynajmniej w programach zaliczeniowych.. zawsze mogą się czepiać, że jest to niebezpieczne i niezgodne ze standardami.. piszę to tylko w ramach ciekawostki..-- 23 paź 2011, o 12:38 --PS jak czegoś nie rozumiesz to wal śmiało.. i bardzo polecam CodeBlocks, dobry wybór

[mario765i]

Ogólnie to program działa. Tylko że po podaniu przedziału wyświetlany jest od razu wynik, a w wymaganiu należy podać najpierw przedziały, a dopiero po ich dodaniu mają być wyświetlane wyniki. Liczba testowanych przedziałów to 1<=N<=20000, a granice przedziałów to 2<=a<=b<=1000000. Po wysłaniu na themisa wyskoczył komunikat "time limit exceeded".

[adambak]

nie znam themisa, ale sporo rozwiązuję zadań na SPOJu i stąd moje pytanie: jesteś absolutnie pewien, że najpierw wymaga się pobrania wszystkich przedziałów i następnie dopiero podanie kolejno odpowiedzi do nich? jest to gdzieś wyraźnie zaznaczone? bo jest to zdecydowanie strata czasu.. wydaje mi się że na większości sprawdzarek online działa to tak samo, czyli: Twój program dostaje z wejścia dane i wypisuje wyjście do pliku, którego zawartość jest potem porównywana z zawartością jaka być powinna.. a więc nie ma znaczenia kiedy wypiszesz swoje wyjście, ewentualnie ma znaczenie czasowo..


jeśli jednak jesteś co do tego pewien, to wystarczy stworzyć tablicę par (a; b) i najpierw w jednej pętli je wczytać, a potem w drugiej iść od początku tej tablicy i po kolei wypisywać odpowiedzi dla przedziałów..


co do TLE no to wszystko zależy jakie masz tam ograniczenia czasowe itp.. optymalizacji jest bardzo dużo począwszy od takich małych jak wspomniana przeze mnie sztuczka w pierwszym poście, po zamienienie cout/cin na scanf/printf, które działają szybciej a skończywszy na zejściu ze złożonością..

testów jest sporo, więc gdyby każdy był testem maksymalnym to faktycznie masakrycznie wolno by to działo.. przerwa na kawę by nie wystarczyła, żeby program się skończył
ja proponuję takie ulepszenie: skoro za każdym razem będziemy odpowiadać stosując tą samą tablicę z sitem no to bez sensu jest iść liniowo ciagle po niej.. lepiej na każde zapytanie odpowiadać w czasie stałym.. w tym celu wprowadzasz dodatkową tablicę intów w której tab[a] gdzie tab to tablica a a to dany indeks informuje nas o tym ile jest liczb pierwszych w przedziale \(\displaystyle{ \left[ 0; \ a\right]}\).. stworzenie takiej tablicy to jedna pętla po stworzeniu sita, a dzięki temu możesz na każde zapytanie w postaci liczb a, b odpowiedzieć w czasie stałym bo będzie to wynik:
tab - tab[a-1]

jedno tylko zaznaczę: uwaga na indeksy! wszystko zależy jak to zrealizujesz w programie..

powodzenia

-- 23 paź 2011, o 13:22 --

po namyśle.. skoro wyskoczył TLE to znaczy, że mam rację co do tej sprawdzarki.. nie baw się z wczytywaniem par a, b a dpiero potem wypisywaniem odpowiedzi, szkoda czasu i kodu.. rób to od razu tak jak napisałem, czyli: wczytujesz i wypisujesz wynik od razu - całość w pętli tyle razy ile wynosi N..

jestem prawie pewien, że taka poprawka optymalizacyjna jak podałem wystarczy, żeby program przeszedł.. czas będzie całkiem przyzwoity..

[mario765i]

Polecenie jest takie:

Kod zadania: DYZIO | Czas: 1 s | Pamięć: 10 MB | Rozwiązane: nie | drukuj

Dyzio jest chłopcem, który bardzo lubi matematykę. Ostatnio poznał bardzo ciekawe liczby, zwane liczbami pierwszymi. Po lekcji został mu jednak bardzo duży niedosyt. Pani wypisała tylko kilka przykładów takich liczb, a Dyzio chciałby poznać je wszystkie. Postanowiłeś pomóc młodemu matematykowi i uświadomić mu, że liczby pierwsze nie występują tak rzadko, jak mu się wydaje. Napisz program, który dla zadanego przez Dyzia przedziału wyznaczy liczbę liczb pierwszych w nim zawartych.
Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20000) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem: W pierwszym i jedynym wierszu zestawu danych znajdują się dwie liczby a i b (2<=a<=b<=1000000), oddzielone pojedynczą spacją, oznaczające odpowiednio początek i koniec przedziału domkniętego, dla którego program będzie wyznaczał ilość liczb pierwszych.
Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest liczba liczb pierwszych znajdujących się w przedziale domkniętym [a,b].
Przykład
Wejście:

2
6 19
12 50

Wyjście:

5
10

Widziałeś mój kod, na chwilę obecną moja wiedza nie pozwala tego zrobić, żeby mieściło się w tych wymaganiach. Jeśli mógłbyś mi pomóc w naniesieniu poprawek to bardzo byś mi pomógł.

[adambak]

uchh.. poprawiając Twój program miałem chwilę załamki.. nazwij tą zmienną globalną b inaczej np B, żeby się nie myliła z tą lokalną w main, bo były problemy.. w końcu dostałem AC Twoim kodem(z oczywiście poprawkami).. a teraz do rzeczy:

znam to zadanie, jest na SPOJu ha, czyli trafiłem ze złożonością, bo rozwiązałem je bardzo dawno temu i właśnie tak jak Ci podałem w poprzednim poście.. przeszło z przyzwoitym czasem.. tak jak powiedziałem, wypisujesz wyniki od razu po wczytaniu kresów przedziałów..

poprawek wbrew pozorom nie będzie wiele i bardzo Cię zachęcam, żebyś je naniósł do kod sam (więcej Ci to da), ja mogę służyć za pomoc w idei programu..

ogólnie wszystko zostawiasz jak było tylko dodajesz kolejną globalną tablicę primes, czyli o takim samym zakresie jak sito, którą po stworzenia sita wykorzystasz.. robisz to co napisałem poprzednio czyli po zrobieniu sita idziesz

Kod: Zaznacz cały

for(i=2; i<=B; i++)

i dzięki informacji o tym czy i jest pierwsze czy nie ustawiasz primes tak aby wskazywało ile jest liczb pierwszych w przedziale \(\displaystyle{ \left[ 0 \ i\right]}\).. ogólnie nasz cel to takie działanie main:

Kod: Zaznacz cały

for(i=0; i<N; i++){
    cin >> a >> b;

    if(a==0)cout<<primes[b];
    else cout<<primes[b]-primes[a-1];
    cout<<endl;
}

widzisz jak dużo zyskaliśmy? na kazde zapytanie odpowiadamy w czasie stałym.. rozumiesz ideę, czemu jest szybciej? jedyne co Ci zostało to stworzenie tablicy primes co u mnie zajmuje 4 linijki.. dasz radę?

[mario765i]

Próbowałem coś tam robić, tak jak napisałeś, ale najwyraźniej robię coś nie tak.

#include<iostream>
#include<string>

using namespace std;

const int b = 1000000;
bool A[b+1];
const int primes = 1000000;

void sitoEratostenesa()
{
int n,p;

for (n=2; n<=b; n++)
A[n] = false;

for (p=2; p*p<=b; p++)
{
if (A[p]==false)
for (n=p*p; n<=b; n=n+p)
A[n] = true;
}
}


bool isPrime(int p)
{
if (A[p]==true) return false;
return true;
}

int i,licznik=0;
for(i=2; i<=B; i++)
{
if ( isPrime(i) )
{
licznik++;
primes = licznik;
}
}

int main()
{
//int licznik, p;
sitoEratostenesa();
int a,b;
int N;
cin >> N;
int tab[N];
int i=0;

for(i=0; i<N; i++){
cin >> a >> b;

if(a==0) cout<<primes;
else cout<<primes-primes[a-1];
cout<<endl;

}
return 0;
}

[adambak]

umieszczaj kod w znacznikach [ code ] [ / code ]..

widziałem szczere chęci napisania programu, więc oto kod po poprawkach:

Kod: Zaznacz cały

#include<iostream>
#include<string>

using namespace std;

const int B = 1000000;
bool A[B+1];
int primes[B+1];

void sitoEratostenesa()
{
  int n,p;
  for (p=2; p*p<=B; p++)
  {
    if (A[p]==false)
      for (n=p*p; n<=B; n=n+p)
        A[n] = true;
  }
}


bool isPrime(int p)
{
  if (A[p]==true) return false;
  return true;
}


int main()
{
  int N;
  int a,b;
  int i,licznik=0;

  sitoEratostenesa();
  for(i=2; i<=B; i++)
  {
    if ( isPrime(i) )
      licznik++;

    primes[i] = licznik;
  }

  cin >> N;
  for(i=0; i<N; i++){
    cin >> a >> b;

    if(a==0) cout<<primes[b];
    else cout<<primes[b]-primes[a-1];
    cout<<endl;

  }
  return 0;
}

oprócz tego, że działa to Ci posprzątałem w kodzie.. przynajmniej na tyle na ile uważałem to za niezbędne(bo zostawiłem tą funkcję isPrime() jak była, mimo, że sam bym inaczej ją napisał, żeby działała bardziej logicznie z tą tablicą sita, ale to też i sito by trzeba było poodwracać względem wartości logicznych więc już tak zostawiłem skoro chciałeś)..



trochę martwią mnie Twoje niektóre błędy, ale rozumiem że jakoś długo nie programujesz?
na przyszłość uwagi co do Twojego kodu:
1. nazewnictwo zmiennych.. const int B miało być po to aby nie kolidowało z małym b w mainie.. wprowadziłeś je w jednym miejscu ale potem już nie, a np w funkcji sita było to konieczne(z resztą nie tylko).. zwróć uwagę gdzie dałem B, a gdzie b..
2. martwiące też jest const int primes = 1000000;.. po pierwsze nie const bo będziesz zmianiał.. poza tym nie pownieneś przypisywać wartości bo tylko deklarujesz tą tablicę, alokujesz jej miejsce w pamięci (przypominam, że jako globalna wypełnia się na starcie zerami)..
3. fragment:

Kod: Zaznacz cały

int i,licznik=0;
for(i=2; i<=B; i++)
{
  if ( isPrime(i) )
  {
    licznik++;
    primes[i] = licznik;
  }
}

był bardzo w nieeleganckim miejscu.. róbmy takie rzeczy w main.. poza tym wciąż do tego fragmentu: sprawdzanie w tym miejscu isPrime(i) nie ma żadnego sensu bo jeszcze się nie wykonało sito.. sito się wykona dopiero w main i wtedy ten test pierwszości będzie miał sens.. i ostatnia uwaga do tych linijek - pomysł jak najbardziej na miejscu, ale wykonanie złe.. mianowicie primes = licznik; powinno być w każdym kroku pętli (dlatego wywaliłem je pod ifa), bo każdej komórce primes trzeba coś przypisać, czasem tylko to będzie liczba o jeden większa, jeśli natrafiliśmy na liczbe pierwszą (uzasadnienie w postach wyżej)..
4. chaos w mainie i niepotrzebna tablica int tab[N]..
5. chyba tyle..



mam nadzieję, że było to jakoś pouczające.. jeśli o wytłumaczeniu czegoś zapomniałem, bądź wciąż coś jest niejasne to pisz..

[mario765i]

Wszystko działa! No i przy okazji dowiedziałem się paru nowych dla mnie rzeczy. Dzięki za wytłumaczenie moich błędów. Jeszcze raz wielkie dzięki!

[adambak]

proszę bardzo