Sprawdzanie czy liczby są parami względnie pierwsze

freak91 · Post autor: **freak91** » 27 wrz 2011, o 18:09

W chińskim twierdzeniu o resztach jest założenie, że wszystkie \(\displaystyle{ m_1, m_2, m_3, ..., m_i}\) muszą być parami względnie pierwsze.

Chciałbym napisać program sprawdzajączy, czy dana tablica zawiera liczby naturalne, które są względnie pierwsze.

Załóżmy, że z kilku równań z kongurencją otrzymuje zbiór:
\(\displaystyle{ \left\{ 3, 5, 7, 11, 8, 3, 5, 3\right\}}\)

Następnie sortuje go rosnąco i wywalam powtarzające się liczby otrzymując:
\(\displaystyle{ \left\{ 3, 5, 7, 8, 11 \right\}}\)

Sprawdzam po kolei czy:
\(\displaystyle{ NWD(3, 5) = 1\\
NWD(3, 7) = 1\\
NWD(3, 11) = 1\\
NWD(3, 8) = 1\\
NWD(5, 7) = 1\\
NWD(5, 8) = 1\\
NWD(5, 11) = 1\\
NWD(7, 8) = 1\\
NWD(7, 11) = 1}\)

Czy to dobry pomysł, tzn. czy dobrze rozumiem sens liczb względnie pierwszych?

chlorofil · Post autor: **chlorofil** » 28 wrz 2011, o 00:19

Algorytm jest poprawny. Zastanawiam się jedynie, czy nie dałoby się tego zrobić szybciej, tak żeby nie trzeba było sprawdzać każdej z każdą. Na pewno można stablicować czynniki, żeby nie trzeba było za każdym razem rozkładać tej samej liczby.

freak91 · Post autor: **freak91** » 28 wrz 2011, o 20:32

Dzięki za pomysł z tablicowaniem i sprawdzenie.