Rozkład liczby

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
czadziej
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 13 lip 2013, o 07:27
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 1 raz

Rozkład liczby

Post autor: czadziej »

Mam następujący problem:

Wyjaśnij , dlaczego przy znajdowaniu rozkładu liczby \(\displaystyle{ n\in N}\) na czynniki pierwsze wystarczy wykonanie operacji dzielenia przez liczby pierwsze z zakresu od 1 do \(\displaystyle{ \sqrt{n}}\) ?
Awatar użytkownika
yorgin
Użytkownik
Użytkownik
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

Rozkład liczby

Post autor: yorgin »

Wynika to z tego, że jeśli \(\displaystyle{ n}\) nie kwadratem liczby naturalnej, to \(\displaystyle{ n=k\cdot l}\), gdzie \(\displaystyle{ k\geq\sqrt{n}}\) oraz \(\displaystyle{ l\leq \sqrt{n}}\)
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Rozkład liczby

Post autor: Zordon »

To stwierdzenie samo w sobie nic nie daje. Nie da się ukryć, że \(\displaystyle{ k=n}\), \(\displaystyle{ l=1}\) spełnia.
Raczej trzeba powiedzieć, że jeśli \(\displaystyle{ n}\) jest złożona, to posiada dzielnik \(\displaystyle{ 1<d\leq \sqrt{n}}\).
Awatar użytkownika
yorgin
Użytkownik
Użytkownik
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

Rozkład liczby

Post autor: yorgin »

Zordon pisze: Raczej trzeba powiedzieć, że jeśli \(\displaystyle{ n}\) jest złożona, to posiada dzielnik \(\displaystyle{ 1<d\leq \sqrt{n}}\).
W zasadzie tylko to nas interesuje - złożoność. Jeśli liczba \(\displaystyle{ n}\) obleje ten test, to w sposób oczywisty \(\displaystyle{ k=n, l=1}\).
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Rozkład liczby

Post autor: Zordon »

Nie wiem za bardzo co teraz argumentujesz. Ja tylko stwierdziłem, że Twój pierwszy post nie bardzo daje odpowiedź na zadane pytanie. Zagadkowe jest też dla mnie, czemu zakładasz w nim, że \(\displaystyle{ n}\) nie jest kwadratem.
Awatar użytkownika
yorgin
Użytkownik
Użytkownik
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

Rozkład liczby

Post autor: yorgin »

By nie komplikować wypowiedzi, chodzi mi o to, co zawarłeś w pierwszym poście.

Co do zakładania, że nie jest kwadratem, gdyby \(\displaystyle{ k=n^2}\), to \(\displaystyle{ k}\) jest w oczywisty sposób złożona i jej dzielnikiem jest \(\displaystyle{ n}\). Jeśli nie jest kwadratem, to w zasadzie nierówności wypisane przeze mnie w pierwszym poście można zastąpić silnymi.
ODPOWIEDZ