Witam!
Potrzebuje programu w pascalu wyszukującego wszystkie dzielniki naturalne dowolnej liczby naturalnej. Nie oczekuje od was "gotowca" (troche muszę sie pomęczyć) , ale brak mi pomysłu na algorytm wyszukujący te dzielniki i wypisujacy je na koncu. Może wspomożecie mnie chociaz schematem blokowym, jakims pomysłem po prostu?Pascala ucze sie dopiero pare dni, więc nie wymagajcie ode mnie za wiele.
Można dzielić tę liczbę przez kolejne liczby od 2 do tej liczby.
Aby to troche przyśpieszyć, to powiem ,że wystartczy jak podzielisz liczbe przez kolejno 2,3, aż do pierwiastka z liczby.
Troche nagmatwałem :|
Np. Masz znaleŹć dzielniki liczby a.
Więc dzielisz ją przez 2, 3, ..., aż do pierwiastka z a (ew. +1).
Liczba jest dzielnikiem, gdy reszta z dzielenia jest równa 0.
Chyba ci wystarczy... :-)
Aż do pierwiastka z a ???
To weźmy liczbę 100, jej pierwiastkiem jest 10, a dzieli się też przez 50... :-/
Najłatwiej:
for i := 1 to a do
if i mod a = 0 then // liczba jest dzielnikiem
a dzieli się też przez 50... :-/
Ale to wykryjesz dzieląc przez 2.
panowie, ale dzieląc 100 przez 2 nie wykryję, ze 100 dzieli sie równiez przez 25 a przeciez 25 jest dzielnikiem naturalnym liczby 100.
Albo ja czegos tu nie kumam. Najprawdopodobniej :)
100 / 4 = 25
Spoko, na pewno będzie do pierwiastka z liczby. Taki jest algorytm. :-P
var
a: Integer;
begin
a := Trunc(Sqrt(liczba)+1);
WriteLn('Dzielniki liczby ', liczba);
for i := 1 to a do
if liczba mod i = 0 then
if i = liczba div i then
Write(i)
else
Write(i, ', ', liczba div i, ', ');
dziękuję wszystkim za podpowiedzi! Wasze rady były naprawdę pomocne! Ijeszcze pytanie do Dryobatesa: "przetłumacz" mi sposób wypisywania ostatecznego wyniku - ostatnia linijka z Twojego kodu; po
wyświetleniu wszystkich dzielników wyświetla się na końcu jeszcze przecinek, ale nie zawsze. Nie przeszkadza mi to specjalnie lecz chciałbym wiedziec za co odpowiada każdy znak w tym programie.
Pozdrawiam i stawiam piwo w podzięce: [browar]
if i = liczba div i then
Write(i)
else
Write(i, ', ', liczba div i, ', ');
Jeżeli dwie ostatnie liczby są takie same (np. 6 i 6, dla 36), to wyświetli jedną i dlatego nie ma przecinka, a jeżeli takie same, to doda.
Akurat przecinek to tutaj jest przez przypadek, bo nie wypisywaniem się zająłem, a generowaniem. Przecinek to tylko dla wygody czytania :)
A opis działania już wcześniej podali moi poprzednicy. Jedyne co jest dodatkowe, to to, że parami wyznacza liczby, gdyż podany wcześniej sposób daje jedynie dzielniki 1..sqrt(liczba), więc co najwyżej połowę z nich. Zwykle liczba ma parzystą liczbę dzielników (ab = c), ale jeżeli jest ona kwadratem jakiejś liczby naturalnej, to ma ich nieparzystą liczbę (aa = c). I tylko po to jest ten dodatkowy parametr i przypadkowy przecinek :)
Można to oczywiście zrobić efektywniej, ale to jedynie wskazówka.
Można dzielić tę liczbę przez kolejne liczby od 2 do tej liczby.
Aby to troche przyśpieszyć, to powiem ,że wystartczy jak podzielisz liczbe przez kolejno 2,3, aż do pierwiastka z liczby.Troche nagmatwałem :|
Np. Masz znaleŹć dzielniki liczby a.
Więc dzielisz ją przez 2, 3, ..., aż do pierwiastka z a (ew. +1).
Liczba jest dzielnikiem, gdy reszta z dzielenia jest równa 0.Chyba ci wystarczy... :-)
Do pierwiasta!!! Liczba całkowita, będąca wynikiem dzielenia też jest dzielnikiem... A poza tym był ostatio post na temat liczb pierwszych... Pomyśl Edek, wiele możesz z tego wyciągnąć dla siebie.
var
a:array of integer; {a tablica dzielników}
b,i:integer; {b- to dzielna}
begin
setlength(a,0); {ale tego chyba nie trzeba}
for i:=2 to trunc(sqrt(b))do
if(b mod i)=0 then
begin
setlength(a,length(a)+1+byte((b div(b div i))<>(b div i)));
if((b div(b div i))<>(b div i)) then a[length(a)-2]:=b div i;
a[length(a)-1]:=b div(b div i)
end
end;
jeżeli b div(b div i)=b div i - to tylko w przypadku, gdy trafimy na pierwiastek b. Na przykład 36/(36/6)=36/6
Algorytm dodaje do tablicy i dzielnik i wynik dzielenia. byte(....) jest tylko zrzutowaniem boola (czy wynik=dzielnikowi) na byte. Żeby nie wsadzać takich samych dwóch liczb. W tablicy dzielniki nie są w kolejności, więc jesli potrzebujesz musisz posortować.