DerSchmetterlig Użytkownik Posty: 18 Rejestracja: 25 gru 2007, o 21:56 Płeć: Mężczyzna Lokalizacja: Gniezno Podziękował: 1 raz Pomógł: 1 raz Liczba dzielników Witam Mam taki problem ze znalezieniem liczby dzielników pewnej liczby. Liczba ta nie jest znana i powstawie poprzez pomnozenie dziesięciu liczb a[n] od 1 do 10 000. Mam napisac program w C++ a tam tablica jest za mala aby sprawdzic liczbe dzielnikow dla tej liczby powstalej przez pomnozenie. I prosba jest w tym jak wyliczyc liczbe dzielnikow pewniej liczby nie znajac tej liczby? Znajac jedynie 10 liczb z ktorych wymnozenia powstala takowa liczba. Wiem ze jest to zwiazane z iloscia wystepowania liczb pierwszych w liczbach sklatowych a[n] PS. Jesli cos jest niejasne to prosze pytac postaram sie wyjasnic Dzieki z gory soku11 Użytkownik Posty: 6607 Rejestracja: 16 sty 2007, o 19:42 Płeć: Mężczyzna Podziękował: 119 razy Pomógł: 1823 razy Liczba dzielników Post autor: soku11 » 25 gru 2007, o 22:15 Nie wiem czy dobrze rozumiem, ale: Skoro pewna liczba l mozna zapisac jako: \(\displaystyle{ l=a_1\cdot a_2\cdot a_3\cdot a_4\cdot a_5\cdot a_6\cdot a_7\cdot a_8\cdot a_9\cdot a_{10}}\) To te kolejne liczby \(\displaystyle{ a_n}\) sa juz jej dzielnikami Wystarczy znalezc dzielniki dzielnikow kazdej z liczb \(\displaystyle{ a_n}\) i powyrzucac identyczne POZDRO DerSchmetterlig Użytkownik Posty: 18 Rejestracja: 25 gru 2007, o 21:56 Płeć: Mężczyzna Lokalizacja: Gniezno Podziękował: 1 raz Pomógł: 1 raz Liczba dzielników Post autor: DerSchmetterlig » 25 gru 2007, o 22:22 wydaje mi sie ze nie za bardzo :/ Bo skoro najpierw dzielnikami np a1 i a3 bylo 3 to dzielnikiem liczby l jest takze 9... Wiec chyba czegos niestety brakuje EDIT poza tym i tak nie znajde dzieki temu liczby dzielnikow bez wyznaczania liczby l bo dzielniki beda sie powtarzac Ktos mi powiedzial ze kluczem do rozwiazania tego sa liczby pierwsze ale nie wiem co dokladnie Rogal Użytkownik Posty: 5405 Rejestracja: 11 sty 2005, o 22:21 Płeć: Mężczyzna Lokalizacja: a z Limanowej Podziękował: 1 raz Pomógł: 422 razy Liczba dzielników Post autor: Rogal » 25 gru 2007, o 22:27 Masz znaleźć dzielniki czy ich ilość? DerSchmetterlig Użytkownik Posty: 18 Rejestracja: 25 gru 2007, o 21:56 Płeć: Mężczyzna Lokalizacja: Gniezno Podziękował: 1 raz Pomógł: 1 raz Liczba dzielników Post autor: DerSchmetterlig » 25 gru 2007, o 22:27 Rogal pisze:Masz znaleźć dzielniki czy ich ilość? Ilość dzielników Rogal Użytkownik Posty: 5405 Rejestracja: 11 sty 2005, o 22:21 Płeć: Mężczyzna Lokalizacja: a z Limanowej Podziękował: 1 raz Pomógł: 422 razy Liczba dzielników Post autor: Rogal » 25 gru 2007, o 22:31 No to sprawa miałaby się dość prosto. Poszczególne dziesięć liczb zapisujemy w postaci kanonicznej, to znaczy \(\displaystyle{ a = p_{1}^{k_{1}} p_{2}^{k_{2}} ... p_{n}^{k_{n}}}\) Gdzie p z indeksami to kolejne liczby pierwsze, a k z indeksami to liczby naturalne wraz z zerem. Wyznaczasz po prostu ciąg k dla każdej z tych liczb, następnie jak mnożymy takie liczby przez siebie, to wykładniki się dodają, więc ostatecznie nasza szukana liczba, to będzie \(\displaystyle{ p_{1}}\) w jakiejś tam potędze razy \(\displaystyle{ p_{2}}\) w jakiejś tam potędze i tak dalej, aż do \(\displaystyle{ p_{n}}\). Znając wszystkie 'jakieś te potęgi' można skorzystać ze wzoru na ilość dzielników takiej liczby, który mówi, że jeśli mamy liczbę naturalną przedstawioną w takiej postaci jak nasze a wyżej, to takie a ma \(\displaystyle{ (k_{1}+1)(k_{2}+1)...(k_{n}+1)}\) dzielników. DerSchmetterlig Użytkownik Posty: 18 Rejestracja: 25 gru 2007, o 21:56 Płeć: Mężczyzna Lokalizacja: Gniezno Podziękował: 1 raz Pomógł: 1 raz Liczba dzielników Post autor: DerSchmetterlig » 25 gru 2007, o 22:42 Wydaje mi się, że rozumiem... ale jak znaleźć \(\displaystyle{ p_{1}}\)... \(\displaystyle{ p_{n}}\) (czyli te liczby pierwsze 'składowe') ? Rogal Użytkownik Posty: 5405 Rejestracja: 11 sty 2005, o 22:21 Płeć: Mężczyzna Lokalizacja: a z Limanowej Podziękował: 1 raz Pomógł: 422 razy Liczba dzielników Post autor: Rogal » 25 gru 2007, o 22:49 Nooo, to Ci się może nie spodobać . Te liczby pierwsze, to wszystkie liczby pierwsze większe od 1 i mniejsze od pierwiastka z 10000, czyli od 100. Można je samodzielnie nawet wyliczyć i przypisać kolejne zmienne albo puścić sobie jakieś miłe Sito Erastotenesa, które zrobi to za nas. W każdym razie trochu dodatkowej roboty jest, ale bardziej efektywnej metody aktualnie nie widzę, a jeśli jest, to będzie tą metodą tylko może bardziej zoptymalizowaną. DerSchmetterlig Użytkownik Posty: 18 Rejestracja: 25 gru 2007, o 21:56 Płeć: Mężczyzna Lokalizacja: Gniezno Podziękował: 1 raz Pomógł: 1 raz Liczba dzielników Post autor: DerSchmetterlig » 25 gru 2007, o 22:53 no tak, Sitem Erastotenesa bez problemu odszukam wszystkie liczby pierwsze od 1 do 100, ale co z potęgą do której podnieść daną liczbę pierwszą? Sito już mam w C++ Ostatnio zmieniony 25 gru 2007, o 23:01 przez DerSchmetterlig, łącznie zmieniany 2 razy. Rogal Użytkownik Posty: 5405 Rejestracja: 11 sty 2005, o 22:21 Płeć: Mężczyzna Lokalizacja: a z Limanowej Podziękował: 1 raz Pomógł: 422 razy Liczba dzielników Post autor: Rogal » 25 gru 2007, o 23:00 No tu sprawa jest równie prosta. Weźmy pierwszą z brzegu liczbę \(\displaystyle{ a_{1}}\). Dzielimy ją sobie przez \(\displaystyle{ p_{1}}\). Jak się podzieliła, to jeszcze raz i tak dalej, aż się nie podzieli. Ilość dzieleń to liczba \(\displaystyle{ k_{1}}\). Każdą następną wyznaczasz tak samo, więc zgrabne dwie pętelki sobie zapuścisz i wszystko wyjdzie DerSchmetterlig Użytkownik Posty: 18 Rejestracja: 25 gru 2007, o 21:56 Płeć: Mężczyzna Lokalizacja: Gniezno Podziękował: 1 raz Pomógł: 1 raz Liczba dzielników Post autor: DerSchmetterlig » 25 gru 2007, o 23:04 Dzięki wielkie już teraz rozumiem jak to zrobić Tylko mam jeszcze jedną kwestię propo zakresu liczby pierwszych Napisałeś, że wystarczy poszukać liczby pierwsze z zakresu od 1 do pierwiastka z 10 000, czyli 100 Ale: np. 35 już nie spełnia tego bo jest to \(\displaystyle{ 7^{1}}\) * \(\displaystyle{ 5^{1}}\) To samo jest np. z 99 Więc nie wiem czy wystarczą liczby od 1 do 100 EDIT Taka sama sytuacja jest w przypadku gdy któreś a jest liczbą pierwszą Rogal Użytkownik Posty: 5405 Rejestracja: 11 sty 2005, o 22:21 Płeć: Mężczyzna Lokalizacja: a z Limanowej Podziękował: 1 raz Pomógł: 422 razy Liczba dzielników Post autor: Rogal » 25 gru 2007, o 23:21 Tego przed editem nie zrozumiałem, prosiłbym jakoś adekwatnie tłumaczyć do tej pory ; ) A co do tego drugiego, to chyba jasny wniosek się nasuwa, że gdy a jest liczbą pierwszą, to trzeba zastosować specjalnie traktowanie i po prostu dopisać ją sobie jako liczbę \(\displaystyle{ p_{n+1}}\) w pierwszej potędzę i potem liczbę dzielników wyznaczać tak samo. DerSchmetterlig Użytkownik Posty: 18 Rejestracja: 25 gru 2007, o 21:56 Płeć: Mężczyzna Lokalizacja: Gniezno Podziękował: 1 raz Pomógł: 1 raz Liczba dzielników Post autor: DerSchmetterlig » 25 gru 2007, o 23:27 Chodzi o to, że napisałeś. iż wystarczy poszukać liczby od 1 do 100 (czyli do pierwiastka z 10 000) A np dla liczby 35 albo 99 nie wystarczą liczby pierwsze do pierwiastka z danej liczby: Pierwiastek z 35 tj. mniej niż 6 a, żeby wyznaczyć liczbę dzielników potrzeba \(\displaystyle{ 5^{1}}\) * \(\displaystyle{ 7^{1}}\) (czyli 7 jest więcej niż pierwiastek z 35) Ale ogólnie to nie będzie większy problem bo liczby pierwsze od 1 do 100 a od 1 do 10 000 przy dzisiejszych procesorach to praktycznie bez różnicy Także wielkie dzięki za pomoc, wiele mi pomogłeś. Pozdrawiam Rogal Użytkownik Posty: 5405 Rejestracja: 11 sty 2005, o 22:21 Płeć: Mężczyzna Lokalizacja: a z Limanowej Podziękował: 1 raz Pomógł: 422 razy Liczba dzielników Post autor: Rogal » 25 gru 2007, o 23:34 Ach no to jasne, że jak się podzieli, to ma dzielnik 'po drugiej stronie' pierwiastka. Zapomniałem o tym. W takim razie najbezpieczniej będzie faktycznie ciąg liczb pierwszych zrobić mniejszy od 10000. Powodzenia.