Znajdywanie liczb pierwszych

Draconis91 · Post autor: **Draconis91** » 20 maja 2009, o 19:58

Witam. Szukam pomocy w związku z pewnym problemem. Jest to zadanie, które polega na znalezieniu trzech liczb korzystając z pewnych informacji. I tak:

Szukane liczby oznaczmy jako p q i r. Są to trzy różne liczby pierwsze.

Dane są trzy równania:

\(\displaystyle{ p \cdot q \cdot r = n}\)

\(\displaystyle{ p + q + r = x - n}\)

\(\displaystyle{ (p-1) \cdot (q-1) \cdot (r-1) = f}\)

Przy czym: x, f i n są dane z góry. Jak znaleźć p, q i r? Za pomoc z góry dziękuję.

Sylwek · Post autor: **Sylwek** » 20 maja 2009, o 20:23

Skąd masz to zadanie? Pytam, gdyż wygląda, jakby było z jakiegoś konkursu.

Draconis91 · Post autor: **Draconis91** » 20 maja 2009, o 20:33

Niby jest. Ale nasza szkoła nie bierze w nim udziału i facet dał nam 10 zadań z jakiegoś "konkursu, w którym poziom zadań jest śmiesznie łatwy jak na klasy licealne" :/ I musimy zrobić te zadania na zaliczenie dodatkowego materiału. 8 już skończyłem, ale tego nie moge ruszyć. Acha, i mam pytanie, bo dzisiaj mój mózg jest absolutnie niesprawny: jeśli mam takie wyrażenie:

\(\displaystyle{ a^{2}b + ab ^{2} = x}\)

to jak wyznaczyć a w zależności od b i x?

snm · Post autor: **snm** » 20 maja 2009, o 20:40

Draconis91 pisze: \(\displaystyle{ a^{2}b + ab ^{2} = x}\)

to jak wyznaczyć a w zależności od b i x?

Słyszałeś o równaniach kwadratowych?

Draconis91 · Post autor: **Draconis91** » 20 maja 2009, o 20:43

Tak, słyszałem. Tylko widzę tutaj coś w rodzaju równania podwójnego drugiego stopnia i nie wiem jak sie za to zabrać.

xanowron · Post autor: **xanowron** » 20 maja 2009, o 20:53

Draconis91 pisze: \(\displaystyle{ a^{2}b + ab ^{2} = x}\)

to jak wyznaczyć a w zależności od b i x?

\(\displaystyle{ a^{2}b + ab ^{2}-x = 0}\)

\(\displaystyle{ a}\) to zmienna, \(\displaystyle{ b,x}\) stałe

\(\displaystyle{ \Delta = b^{4}+4bx}\) itd.

Draconis91 · Post autor: **Draconis91** » 20 maja 2009, o 21:40

Ok, wracając jednak do zadania:

Finalnie otrzymałem taką postać:

\(\displaystyle{ p + q + r = x - p \cdot q \cdot r}\)

Co najlepsze pqr jest mi znane, x także, więc suma również przy czym p, q i r są pierwsze. Jak je szybko znaleźć, jeśli p,q,r < 1.000.000?

Bo patrzę na ten zapis i czuje że mam gotową odpowiedź ale nie wiem jak to wykorzystać

Sylwek · Post autor: **Sylwek** » 21 maja 2009, o 00:02

Ponieważ n masz dane, to z równości: \(\displaystyle{ n=pqr}\):
a) jeśli n jest iloczynem trzech różnych liczb pierwszych, czyli: \(\displaystyle{ n=abc}\), (a<b<c) wyznaczyć: \(\displaystyle{ p=a, \ q=b, \ r=c}\) (gdy, dla ustalenia uwagi, bo kolejność nie jest ważna, p<q<r)
b) jeśli n nie jest iloczynem trzech różnych liczb pierwszych, to powyższe równanie jest sprzeczne

A potem wystarczy sprawdzić, czy wyznaczone wartości p,q,r spełniają pozostałe równania tego układu (w sumie nie wiem po co tyle równań, bo tylko z pierwszego korzystałem - pozostałe z pewnością są po to, aby trzeba było sprawdzić, czy nie stoją one w sprzeczności z wyliczonym rozwiązaniem).

Jak widzisz, przy teoretycznie losowych liczbach n,x,f nie powinno być rozwiązań, chociaż oczywiście istnieją takie liczby n,x,f, że ten układ ma rozwiązanie.