Wyszukiwanie największej liczby względnie pierwszej w pliku tekstowym

0

w liczby.txt znajduję się 200 różnych liczb całkowitych <2, 1.000.000>, każda w osobnym wierszu
Polecenie jest takie: 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.

int nwd(int x, int y) //algorytm euklidesa
{
    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[200];
    for(int i=0; i<200; i++)
    {
        int a;
        in >> liczby[i];
    }
    int najwieksza = 0;
    for(int i=0; i<200; i++)
    {
        bool ok = true;
        for(int j=0; j<200; j++)
            if (i != j && nwd(liczby[i],liczby[j])>1) //******** warunek i!=j ??
                ok = false;
        if (ok && liczby[i] > najwieksza)
            najwieksza = liczby[i];
    }
    out << "Najwieksza wzglednie pierwsza: " << najwieksza << endl;
}

Moje pytanie jest takie: Dlaczego konieczny jest warunek i!=j ?
Jeżeli to będzie ta sama liczba, to i tak jej nwd jest większy od 1, w konsekwencji otrzymamy ok=false.
Jest on niezbędny, gdyż w przeciwnym razie wychodzi inny wynik.

0

Nie jest konieczny, ale zwiększa czytelność kodu (kiepskie wytłumaczenie) oraz delikatnie poprawia efektywność.

0

Bez tego warunku program podaje błędny wynik

1

Jeśli nie Dasz tego warunku, to ok będzie miało zawsze, po obiegu pętli wewnętrznej, wartość false - bo gcd(n, n) = n > 1, więc, dalej, warunek w kolejnym if - ie, (tym w pętli zewnetrznej) zawsze będzie false, czyli ten algorytm nic nie będzie robił.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0