Matura z informatyki 2009 - zadanie 5

Napisał: Blacksword; Piątek, 19.06.2009; 18:14

Kategoria: Matura z Informatyki 2009 - Podstawa - Rozwiązania zadań.

Zadanie 5. Liczby pierwsze (8 pkt)

Liczba pierwsza to liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: 1 i samą siebie.

Przykłady liczb pierwszych:

7
11
29

Liczba 21 nie jest liczbą pierwszą, ponieważ oprócz liczby 1 i 21 jej dzielnikami są także 3 i 7.

W pliku o nazwie liczby.txt umieszczono w kolejnych wierszach 500 liczb całkowitych dodatnich, po jednej w wierszu, z których każda liczba ma co najwyżej 6 cyfr. Napisz program, za pomocą którego otrzymasz tylko te liczby z pliku liczby.txt, które są kwadratami liczb pierwszych. Na przykład liczba 49 jest kwadratem liczby pierwszej – 49 = 72 . Wyniki zapisz w pliku zad_5.txt. Twój program powinien działać poprawnie również wtedy, gdy plik liczby.txt będzie zawierał 500 innych liczb całkowitych dodatnich, o co najwyżej 6 cyfrach, każda liczba w osobnym wierszu.

Do tego zadania można podejść na kilka sposobów. Pierwszy, który przychodzi na myśl mógłby wyglądać tak:

Algorytm raczej niezbyt skomplikowany, obliczenie pierwiastka załatwimy funkcją sqrt() z biblioteki cmath, a dodatkowo wykorzystamy algorytm sprawdzający czy dana liczba jest pierwsza.

Kod programu rozwiązującego to zadanie mógłby więc mieć taką postać:

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>

using namespace std;

int liczby[500];

void wczytaj_liczby(char* nazwa_pliku);
void wypisz_liczby(char* nazwa_pliku);
bool czypierwsza(int liczba);

int main()
{
 wczytaj_liczby("liczby.txt"); //wczytujemy liczby z pliku liczby.txt
 //wypisz_liczby("wynik.txt");
 ofstream wynik("wynik_5.txt");
 for (int i = 0; i < 500; i++)
    {
     double pierwiastek = sqrt(liczby[i]); //liczymy pierwiastek z liczby
     double rozwiniecie = pierwiastek - int(pierwiastek); //int() zaokrągla w doł, 
	 //a więc wynikiem odejmowania jest liczba mieszcząca się w przedziale <0.0;1)
     if (rozwiniecie == 0.0) //jeżeli nie było części po przecinku (pierwiastek jest naturalny
            {
             if (czypierwsza(int(pierwiastek)) == true) //sprawdzamy pierwszość
                    {
                     wynik << liczby[i] << endl; //i wypisujemy te które trzeba
                    }
            }
    }
 wynik.close();

 return 0;
}

void wczytaj_liczby(char* nazwa_pliku)
{
 ifstream dane(nazwa_pliku); //otwieramy strumień odczytu z pliku
 char liczba[7]; //tablica, w której będziemy przechowywać pojedynczą liczbę
 //wiemy że każda liczba ma swój oddzielny wiersz, ma nie więcej niż 6 znaków
 //oraz że liczb jest równo 500
 for (int i = 0; i < 500; i++)
    {
     //wczytujemy liczbe jako ciąg znaków
     dane.getline(liczba, 7);
     //a teraz przekształcamy ją na liczbę całkowitą długą
     //używamy do tego funkcji atoi() z biblioteki cstdlib
     liczby[i] = atoi(liczba);
     //teraz operujemy już na liczbach a nie na znakach
    }
 dane.close();
}

void wypisz_liczby(char* nazwa_pliku)
{
 ofstream wynik(nazwa_pliku);
 for (int i = 0; i < 500; i++)
        wynik << liczby[i] << " " << liczby[i]+liczby[i] << endl;
 wynik.close();
}

bool czypierwsza(int liczba)
{
 if (liczba == 1) return false;
 int pierw = int(sqrt(liczba));
 for (int i = 2; i <= pierw; i++)
    {
     if (liczba % i == 0) return false;
    }
 return true;
}

Komentarze w programie powinny wyjaśniać co i jak działa. Nie jest to jednak jedyne podejście do tego problemu. Można również wykorzystać fakt, że liczb pierwszych jest bardzo mało. Zajmiemy się tu nieco tzw. preprocessing'iem.

Wiemy, że liczby w danych są maksymalnie 6 cyfrowe. Będziemy natomiast szukać liczb pierwszych, które podniesione do kwadratu dadzą nam taką liczbę. Słowem, wystarczyłoby gdybyśmy znaleźli wszystkie liczby pierwsze w zakresie od 2 do 1000. Wtedy, zamiast sprawdzać czy pierwiastek z danej liczby jest pierwszy, moglibyśmy go wyszukiwać we wcześniej przygotowanym zbiorze (np. binarnie - dzięki temu moglibyśmy znajdować ją zadając maksymalnie 8 pytań, a nie sprawdzając wszystkie po kolei). Tak naprawdę, w tym zadaniu zysk, jaki byśmy mogli dzięki temu osiągnąć, jest właściwie nie zauważalny, możnaby się nawet kłócić, czy nie byłby to wolniejszy sposób. Jednak warto się czasem zastanowić, czy nie lepiej jest pewne informacje dostarczyć sobie do programu wcześniej, jeszcze przed jego uruchomieniem.

To całość rozwiązania zadania piątego z matury 2009. Wszelkie pytania, znalezione błędy, oraz propozycje innych rozwiązań proszę kierować na nasze forum w TYM temacie.