Liczby pierwsze w Trójkolandii - zadanie maturalne

Witajcie, rozwiązuje zadanie maturalne o poniższej treści:

W Trójkolandii za liczby naturalne uznaje się tylko te liczby całkowite dodatnie, które w wyniku dzielenia przez 3 dają resztę 1, tzn.: 1, 4, 7, 10, 13, 16, 19, 22, 25, 28...

Aby liczba n > 1 była liczbą pierwszą w Trójkolandii, musi spełniać następujące warunki:

• reszta z dzielenia n przez 3 jest równa 1,
• wszystkie dzielniki liczby n (poza n oraz 1) dzielone przez 3 dają resztę różną od 1,
czyli liczba n nie ma dzielników (poza 1 i n), które w Trójkolandii są traktowane jak liczby naturalne. Przykładami liczb uznawanych w Trójkolandii za pierwsze są: 4, 10, 22 i 25, ponieważ nie mają one dzielników (mniejszych od nich samych i większych od 1), które przy dzieleniu przez 3 dają resztę 1, ale liczba 16 nie jest w Trójkolandii pierwsza (bo ma dzielnik 4).

Napisz program, który wypisze w pliku zadanie4.txt:

a) liczbę liczb pierwszych w Trójkolandii w przedziale [1, 20]
b) liczbę liczb pierwszych w Trójkolandii w przedziale [21, 1000]
c) liczbę liczb pierwszych w Trójkolandii w przedziale [1001, 1000000]
d) liczbę liczb pierwszych w Trójkolandii w przedziale [1000001, 10000000].

Dla podpunktów a i b otrzymuję poprawne wartości, odpowiednio: 5 oraz 168. Natomiast dla c i d mam złe, odpowiednio: 98326 (powinno być 1797), 765815 (a tutaj 862344).

Szczerze mówiąc nie wiem czy popełniłem jakiś błąd w rozumieniu zadania, czy źle napisałem program, proszę Was o pomoc. :)

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

bool pierwsza (int i)
{

    if(i<=1)
    {
            //cout<<i<<endl;
        return false;
    }

if(i%3!=1)//je¿eli nie jest naturalna(w trojkolandii)
{    //cout<<i<<endl;

    return false;
}

for(int j=2;j*j<=i;j++)
{


if(j%3==1)
{
if(i%j==0)
{

    return false;
}
}

}

//cout<<i<<endl;

return true;
}

int liczbypierwsze(int p,int k)
{
    int licznik=0;

    for(int i=p;i<=k;i++)
    {
        if(pierwsza(i))
            licznik++;
    }

return licznik;
}

int main()
{
int a,b,c,d;
a=liczbypierwsze(1,20);
b=liczbypierwsze(21,1000);
c=liczbypierwsze(1001,1000000);
d=liczbypierwsze(1000001,10000000);


cout<<a<<endl;
cout<<b<<endl;
cout<<c<<endl;
cout<<d<<endl;

system("PAUSE");
return 0;
}

gruntowne sformatowanie treści posta - furious programming

zacznijmy od tego:

for(int i=p;i<=k;i++)

jak to się ma do "W Trójkolandii za liczby naturalne uznaje się tylko te liczby całkowite dodatnie, które
w wyniku dzielenia przez 3 dają resztę 1, tzn.: 1, 4, 7, 10, 13, 16, 19, 22, 25, 28... "
?

dodanie znacznika <code class="cpp"> - furious programming

for(int i=p;i<=k;i++)

Odpowiada za to, aby sprawdzać każdą liczbę z zakresu przy użyciu funkcji pierwsza(i) , gdzie jest sprawdzana m.in. pod kątem tego czy dzielenie jej przez 3 daje resztę 1.

Za rozwiązanie takie jak podałeś powinno się nie zaliczyć tej matury z programowania. Poniżej cały działający kod:

#include <iostream>
using namespace std;

unsigned CountBefore(unsigned N) { return (N-1)/3+1; }
unsigned CountBetween(unsigned A,unsigned B) { return CountBefore(B)-(A>1?CountBefore(A-1):0); }

int main()
  {
   cout<<CountBetween(1,20)<<endl;
   cout<<CountBetween(21,1000)<<endl;
   cout<<CountBetween(1001,1000000)<<endl;
   cout<<CountBetween(1000001,10000000)<<endl;
   cin.get(); // jeżeli tego potrzebujesz to zmień IDE
   return 0;
  }

Dziękuję, tylko wyniki jak poniżej zwracane przez ten program nie mają zbytniego związku z tym co jest w kluczu odpowiedzi... :(
2863311537 327 333000 3000000

@_13th_Dragon

Ale Twoje rozwiązanie nie oblicza ilości liczb pierwszych w Trójkolandii, tylko ilośc liczb naturalnych w Trójkolandii.

@_13th_Dragon Niemożliwe, że w przedziale [1, 20] jest 7 liczb pierwszych. W takim wypadku musiałyby to być wszystkie liczby naturalne w tym przedziale w Trójkolandii. :)

@gośćabc a mógłbyś mi pokazać jak Ty napisałeś swój kod? Bo jestem ciekawy.

#include <iostream>
#include <cmath>

bool pierwsza(unsigned koniec)
{
	if(koniec == 1)
		return false;

	unsigned maxDzielnik = std::sqrt(koniec);
	for(unsigned i = 4 ; i <= maxDzielnik ; i += 3) {
		if(!(koniec % i))
			return false;
	}

	return true;
}

unsigned calculate(unsigned poczatek, unsigned koniec)
{
	int reszta = poczatek % 3;
	if(reszta == 0)
		poczatek += 1;
	else if(reszta == 2)
		poczatek += 2;

	int counter = 0;
	for(unsigned i = poczatek ; i <= koniec ; i += 3)
		if(pierwsza(i))
			++counter;

	return counter;
}

int main()
{
	std::cout << calculate(1,20) << std::endl;
	std::cout << calculate(21,1000) << std::endl;
	std::cout << calculate(1001,1000000) << std::endl;
	std::cout << calculate(1000001,10000000) << std::endl;

	return 0;
}

dziwne, abyś liczył źle c i d jak a i b jest dobrze

@gośćabc @Pawlllosss

Mam takie same wyniki, rozwiązanie jak gośćabc.
Albo błąd w odpowiedziach, albo o co innego chodzi :D

Skoro 3 osobom wyszło to samo, to chyba po prostu zły klucz odpowiedzi opublikowali, chyba, że ktoś jeszcze wpadł na inny sposób i napisze :P. Tak czy siak dzięki, przynajmniej dowiedziałem się jak można było napisać ten program bardziej optymalnie.

To zadanie da się rozwiązać jakimiś funkcjami eulera albo innego. To co podaliscie z petla to rozwiazanie naiwne. Trojkolandia to nic innego jak przestrzen mod 3. Robiliśmy na studiach takie na wejsciowkach zadania.

Ale to ma chyba tylko wpływ na wydajność programu, prawda?

Tak. Jeśli to zadanie maturalne to naiwna implementacja jest jak najbardziej wystarczająca.