Liczba dzielników

DerSchmetterlig · Post autor: **DerSchmetterlig** » 25 gru 2007, o 22:04

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 · 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 · 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 · Post autor: **Rogal** » 25 gru 2007, o 22:27

Masz znaleźć dzielniki czy ich ilość?

DerSchmetterlig · Post autor: **DerSchmetterlig** » 25 gru 2007, o 22:27

Rogal pisze:Masz znaleźć dzielniki czy ich ilość?

Ilość dzielników

Rogal · 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 · 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 · 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 · 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++

Rogal · 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 · 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 · 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 · 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 · 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.