Liczby pierwsze w Trójkolandii - zadanie maturalne

Liczby pierwsze w Trójkolandii - zadanie maturalne
PA
  • Rejestracja:ponad 10 lat
  • Ostatnio:prawie 9 lat
  • Postów:6
0

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. :)

Kopiuj
#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

edytowany 1x, ostatnio: flowCRANE
flowCRANE
Jakbyś jeszcze się nie zorientował to może podpowiem - przeglądarki od niepamiętnych czasów bez problemu radzą sobie z łamaniem wierszy, więc nie musisz co 50 znaków wstawiać entera...
gośćabc
  • Rejestracja:prawie 11 lat
  • Ostatnio:ponad 3 lata
  • Lokalizacja:Szczecin
  • Postów:500
0

zacznijmy od tego:

Kopiuj
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

edytowany 1x, ostatnio: flowCRANE
PA
  • Rejestracja:ponad 10 lat
  • Ostatnio:prawie 9 lat
  • Postów:6
0
Kopiuj
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.

edytowany 1x, ostatnio: flowCRANE
flowCRANE
I wstawiaj kod w znaczniki kolorując składnię; Jeśli nie wiesz jak się to robi, to zaglądnij do tego artykułu - Formatowanie treści postów na forum
gośćabc
ale po co iterować po wszystkich i sprawdzać każdą liczbę, skoro możesz zrobić to raz i zmodyfikować początek przedziału i zwiększać indeks co 3;
_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:2 miesiące
0

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

Kopiuj
#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;
  }

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 2x, ostatnio: _13th_Dragon
_13th_Dragon
Brak dwóch znaków.
gośćabc
fajnie, że masz 7 liczb z przedziału 1, 20 jak jest ich 5 dalej nie chce mi się sprawdzać
_13th_Dragon
fajnie jest to że przewagarowałeś liczenie do 7-miu: 1, 4, 7, 10, 13, 16, 19 dobra nie doczytałem - to jest sprawdzenie na naturalność.
gośćabc
"naumn" się czytać polecenia zadań i mnie nie denerwuj
PA
  • Rejestracja:ponad 10 lat
  • Ostatnio:prawie 9 lat
  • Postów:6
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

1

@_13th_Dragon

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

Wylte
  • Rejestracja:prawie 11 lat
  • Ostatnio:ponad 10 lat
  • Lokalizacja:hogwartIOkolice
  • Postów:30
0

@_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. :)

edytowany 2x, ostatnio: Wylte
gośćabc
mi wyszło tak jak Tobie http://i.imgur.com/ZgE19JH.png więc chyba błąd w odp
PA
  • Rejestracja:ponad 10 lat
  • Ostatnio:prawie 9 lat
  • Postów:6
0

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

edytowany 1x, ostatnio: Pawlllosss
gośćabc
  • Rejestracja:prawie 11 lat
  • Ostatnio:ponad 3 lata
  • Lokalizacja:Szczecin
  • Postów:500
2
Kopiuj
#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

edytowany 1x, ostatnio: gośćabc
0

@gośćabc @Pawlllosss

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

PA
  • Rejestracja:ponad 10 lat
  • Ostatnio:prawie 9 lat
  • Postów:6
0

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.

gośćabc
tam pododawaj klamerek do ifów i for, bez nich to jest niezbyt czytelne dla człowieka
0

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.

PA
  • Rejestracja:ponad 10 lat
  • Ostatnio:prawie 9 lat
  • Postów:6
0

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

edytowany 1x, ostatnio: Pawlllosss
kq
Moderator C/C++
  • Rejestracja:ponad 11 lat
  • Ostatnio:około 15 godzin
  • Lokalizacja:Szczecin
1

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


Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)