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?
Rozłóż liczbę na czynniki
-
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Rozłóż liczbę na czynniki
Ostatnio zmieniony 20 kwie 2021, o 22:20 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- kmarciniak1
- Użytkownik
- Posty: 809
- Rejestracja: 14 lis 2014, o 19:37
- Płeć: Mężczyzna
- Podziękował: 48 razy
- Pomógł: 183 razy
-
- Użytkownik
- Posty: 466
- 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
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}\)
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}\)