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}}\) ?
Rozkład liczby
- yorgin
- 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
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}}\)
- Zordon
- 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
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}}\).
Raczej trzeba powiedzieć, że jeśli \(\displaystyle{ n}\) jest złożona, to posiada dzielnik \(\displaystyle{ 1<d\leq \sqrt{n}}\).
- yorgin
- 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
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}\).Zordon pisze: Raczej trzeba powiedzieć, że jeśli \(\displaystyle{ n}\) jest złożona, to posiada dzielnik \(\displaystyle{ 1<d\leq \sqrt{n}}\).
- Zordon
- 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
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.
- yorgin
- 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
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.
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.