Rozłóż liczbę na czynniki

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Rozłóż liczbę na czynniki

Post autor: max123321 »

Mamy że \(\displaystyle{ n = ab}\) , gdzie \(\displaystyle{ a \ge b > 0}\) implikuje, że \(\displaystyle{ n = \left( \frac{a+b}{2}\right)^2 − \left( \frac{a-b}{2}\right)^2}\). Wykorzystać to do rozkładu liczby liczby \(\displaystyle{ 200819}\) na czynniki pierwsze. Czy można rozszerzyć te idee dla znalezienia rozkładu liczby \(\displaystyle{ 141467}\)? Jaka jest złożoność odpowiedniego algorytmu w zależności od różnicy między dzielnikami pierwszymi \(\displaystyle{ p, q}\) liczby \(\displaystyle{ n}\)?

Jak to zrobić? Może mi ktoś pomóc?
Ostatnio zmieniony 20 kwie 2021, o 22:20 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
kmarciniak1
Użytkownik
Użytkownik
Posty: 809
Rejestracja: 14 lis 2014, o 19:37
Płeć: Mężczyzna
Podziękował: 48 razy
Pomógł: 183 razy

Re: Rozłóż liczbę na czynniki

Post autor: kmarciniak1 »

\(\displaystyle{ 200819=450 ^{2}-41 ^{2} }\)
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Rozłóż liczbę na czynniki

Post autor: Brombal »

Przedstawmy \(\displaystyle{ a=b+ \partial }\)
Ponieważ \(\displaystyle{ n}\)-nieparzyste to \(\displaystyle{ a}\) i \(\displaystyle{ b}\) - nieparzyste.
Z tego wynika, że \(\displaystyle{ \partial}\) parzyste.
Po podstawieniu \(\displaystyle{ b= \frac{ \sqrt{ \partial ^{2}+4n }- \partial }{2} }\).
Warunkiem wystarczającym by \(\displaystyle{ b}\) było liczbą całkowitą i nieparzystą jest to by wyrażenie \(\displaystyle{ \sqrt{ \partial ^{2} +4n} }\) było liczbą całkowitą parzystą . (Co ciekawe \(\displaystyle{ \sqrt{ \partial ^{2} +4n} - \partial }\) jest zawsze pierwszego stopnia parzystości dla \(\displaystyle{ n}\)- nieparzystego i \(\displaystyle{ \partial }\) - parzystego).
Dlatego poszukujemy wartości parzystych dla wyrażenia \(\displaystyle{ \sqrt{ \partial ^{2} +4n} }\) dla których \(\displaystyle{ \partial }\) jest parzyste.
Dla liczby \(\displaystyle{ 200819}\)
Startujemy od \(\displaystyle{ \partial =0}\).
\(\displaystyle{ \sqrt{ 0^{2} +4*200819}=896,2566597 }\).
Najbliższa parzysta liczba \(\displaystyle{ x>896,2566597 }\) , \(\displaystyle{ x=\sqrt{ \partial ^{2} +4n}=898}\)
Dla \(\displaystyle{ x= 898}\), \(\displaystyle{ \partial =55,92852582}\) czyli nie jest całkowity.
Następne \(\displaystyle{ x= 900}\), \(\displaystyle{ \partial =82}\) - spełnia warunek.
Dla \(\displaystyle{ \partial =82}\), \(\displaystyle{ b=409}\) skąd \(\displaystyle{ a= \frac{n}{b}= \frac{200819}{409} =491}\)

Dla liczby \(\displaystyle{ 141467}\)
\(\displaystyle{ \partial =0}\), \(\displaystyle{ x= 752,2419823}\)
Najbliższa jest \(\displaystyle{ x= 754 }\)
Warunek spełnia dopiero 37 sprawdzenie
\(\displaystyle{ x=828}\), \(\displaystyle{ \partial =346}\), \(\displaystyle{ b=241}\), \(\displaystyle{ a=587}\)
Elayne
Użytkownik
Użytkownik
Posty: 926
Rejestracja: 24 paź 2011, o 01:24
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 75 razy
Pomógł: 274 razy

Re: Rozłóż liczbę na czynniki

Post autor: Elayne »

Rozkład liczby \(\displaystyle{ 141 \ 467}\) można zoptymalizować.
ODPOWIEDZ