Zadanie maturalne

60.2
Wśród liczb występujących w pliku wejściowym znajdź te, które mają dokładnie 18 dzielników naturalnych (wliczając w nie 1 i samą liczbę). Dla każdej znalezionej liczby wypisz, oprócz jej wartości, listę wszystkich jej dzielników, posortowaną rosnąco.

60.3
Znajdź największą liczbę w pliku, która jest względnie pierwsza ze wszystkimi pozostałymi, czyli taką, która z żadną z pozostałych liczb nie ma wspólnego dzielnika innego niż 1.

Pierwsze rozwiązanie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <fstream>

using namespace std;

const int rozmiar = 200;


int nwd(int x, int y)
{
    if (x < y)
        return nwd(y,x);
    if (y == 0)
        return x;
    return nwd(y,x%y);
}

int main()
{
    ifstream in("liczby.txt");
    ofstream out("wyniki.txt",fstream::app);
    int liczby[rozmiar];
    for(int i=0; i<rozmiar; i++)
    {
        int a;
        in >> liczby[i];
    }
    int najwieksza = 0;
    for(int i=0; i<rozmiar; i++)
    {
        bool ok = true;
        for(int j=0; j<rozmiar; j++)
            if (i != j && nwd(liczby[i],liczby[j])>1)
                ok = false;
        if (ok && liczby[i] > najwieksza)
            najwieksza = liczby[i];
    }
    out << "Najwieksza wzglednie pierwsza: " << najwieksza << endl;
}

Drugie rozwiązanie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

vector <int> rozloz_liczbe(int n) {

    vector <int> wynik;
    for(int i=1;i<=n;i++) {
        if(n % i == 0) {
            wynik.push_back(i);
        }
    }

    return wynik;
}


struct liczba {
    int n;
    vector <int> dzielniki;
};


int main()
{
    vector <struct liczba> rozlozone;

    //60.2
    fstream file;
    file.open("liczby.txt", std::fstream::in | std::fstream::out | std::fstream::app);

    int n;
    while (file >> n) {

        struct liczba wprowadzany;
        wprowadzany.n = n;
        wprowadzany.dzielniki = rozloz_liczbe(n);

        if(wprowadzany.dzielniki.size() == 18) {
            cout<<n<<endl;
            for(vector <int>::iterator it = wprowadzany.dzielniki.begin(); it != wprowadzany.dzielniki.end(); ++it) {
                cout<<*it<<" ";
            }
            cout<<endl;
        }
        rozlozone.push_back(wprowadzany);
    }



    //60.3
    int najwieksza = 0;

    for(vector <struct liczba>::iterator it = rozlozone.begin(); it != rozlozone.end(); ++it) {
        bool f = true;

        for(vector <int>::iterator jt = it->dzielniki.begin(); jt != it->dzielniki.end(); ++jt) {


            for(vector <struct liczba>::iterator y = rozlozone.begin(); y != rozlozone.end(); ++y) {
                for(vector <int>::iterator z = y->dzielniki.begin(); z != y->dzielniki.end(); ++z) {


                    if(*jt > 1 && *z > 1 && it->n != y->n) {
                           
                        if(*jt == *z) {

                            f = false;
                        }
                    }

                }
            }

        }

        if(f == true && it->n > najwieksza) {
            najwieksza = it->n;
        }

        //break;
    }

    cout<<"\n\nNajwieksza wzglednie pierwsza: "<<najwieksza;


    return 0;
}
C

Tagged in:

, ,