Algorytm sprawdzający czy podana liczba ma przynajmniej 3 dzielniki

Odpowiedz Nowy wątek
2011-09-21 21:29
0

Czesc chciałem sie was spytac czy dobrze zrobilem schemat blokowy do algorytmu "Algorytm sprawdzający czy podana liczba ma przynajmniej 3 dzielniki"

Oto moje dzielo http://fotoo.pl/zdjecia/files/2011-09/328079d7.jpg

edytowany 3x, ostatnio: kaluza88, 2011-09-21 21:30
Regulamin: Temat wątku powinien w sposób sensowny i w miarę wyczerpujący opisywać Twój problem. Tak, aby potem wyszukiwarki nie miały kłopotu ze znalezieniem szukanego tekstu. Wątki opatrzone jednowyrazowym tematem, lub zdaniem nie opisującym zupełnie problemu, będą usuwane. - madmike 2011-09-21 22:01

Pozostało 580 znaków

2011-09-21 21:30
Rev
0

Lol, bez przesady, w schemacie blokowym nie chodzi o to, żeby wkleić algorytm do jednego z nich.


ale zauważ ile czasu zaoszczędził przy rysowaniu. Czyż to nie jest praktyczne podejście?:P - allocer 2011-09-21 21:32

Pozostało 580 znaków

2011-09-21 21:32
0

To wez pomoz, bo pani mi to zadala na 1 lekcji, a moi kumple podostawali o wiele latwiejsze.

Kto mi powie, dlaczego w Chromium 16 dostaję 403? :-> - Endrju 2011-09-21 21:35
zabezpieczenie przed hotlinkowaniem po referrerze. - Rev 2011-09-21 21:38
Smutny pomysł. :-( - Endrju 2011-09-21 21:39
Istnieje od zawsze, wcześniej prawie każdy serwis miał to zaimplementowane. - Rev 2011-09-21 21:40

Pozostało 580 znaków

2011-09-21 21:39
Rev
0
kaluza88 napisał(a)

To wez pomoz, bo pani mi to zadala na 1 lekcji, a moi kumple podostawali o wiele latwiejsze.

50zł. Jak chętny jesteś to pisz PW.


Pozostało 580 znaków

2011-09-21 21:40
0

To ma byc ironia czy cos? Algorytm dla calkiem poczatkujacych, ale dobra widze, ze nawet podpowiedzi czy cos nie dostane.

Dla początkujących - dlatego 50zł, a nie 500. - Rev 2011-09-21 21:41
To przynajmniej nakieruj mnie jakos, bo te smieszne 50 zl to ... - kaluza88 2011-09-21 21:44

Pozostało 580 znaków

2011-09-21 21:48
Rev
0

Musisz rozłożyć ten algorytm. Przede wszystkim masz tam pętlę. Strzałeczki musisz porobić do góry. Na pewno miałeś na lekcji.


Pozostało 580 znaków

2011-09-21 22:04
0

Teraz jest dobrze?
http://fotoo.pl/zdjecia/files/2011-09/b1f75d23.jpg

edytowany 1x, ostatnio: kaluza88, 2011-09-21 22:05

Pozostało 580 znaków

2011-09-21 22:28
Rev
0

To mnożenie rozbij na pętlę (warunek sprawdzający czy się zakończyła).


Pozostało 580 znaków

2011-09-22 07:44
bo
0

Nie znam Twojego nauczyciela, ale moim zdaniem schematu blokowego nie ma. W jaki sposób uzyskujesz rozkład liczby n na czynniki pierwsze?
Btw, czy konieczne jest sprawdzanie, że wykładniki są liczbami naturalnymi.

Pozostało 580 znaków

2011-09-22 10:22
0

81nYX :-)

Pokaż pozostałe 4 komentarze
Ja bym nie rozkładał na czynniki, tylko szukał w przedziale [2,floor(sqrt(n))) dzielników liczby n. Po znalezieniu dwóch wypisałbym, że są co najmniej trzy dzielniki, w przeciwnym wypadku, że nie ma. - bogdans 2011-09-22 14:43
wystarczy znaleźć jeden czynnik, jeżeli n/c>1 ...., czyli wystarczy sprawdzić czy... a to robi się nawet zyliony razy szybciej. - Xitami 2011-09-22 16:50
n=15, znajduje czynnik c=3, n/c=5>1, jaki jest trzeci dzielnik? - bogdans 2011-09-22 17:28
skoro odrzucamy dzielniki 1 oraz "n" - to jednak trzeba znaleźć jakiś dzielnik. Wystarczy jeden (szukając w naiwny sposób będzie liczbą pierwszą) i sprawdzić czy iloraz jest liczbą pierwszą. Można by użyć jakiejś dowcipniejszej metody faktoryzacji i sprawdzić pierwszość dzielnika i ilorazu. - Xitami 2011-09-22 17:44
nie wystarczy złożoność, trzeba sprawdzić czy nie jest kwadratem liczby pierwszej - Xitami 2011-09-22 17:55

Pozostało 580 znaków

2011-09-22 18:11
0

Taki kod

        int gr;
        int ile;
        int factor;
        for(int i=2;i<=upperBound;i++)
        {
            gr=(int)Math.sqrt(i);
            ile=0;
            factor=2;
            while(ile<2 && factor<=gr)
            {
                if((i % factor)==0)
                {
                    ile++;
                }
                factor++;
            }
        }

wykonuje się u mnie (dla upperBound=10 mln.) około 1,5 sekundy.
Ulepszenie polegające na tym, że po znalezieniu pierwszego dzielnika d wykonujemy dzielenie j=i/d i szukamy dzielnika >=d, różnego od d dla liczby j skraca czas dwukrotnie.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
Dodam, że ulepszony algorytm nie tylko jest szybszy,a le w odróżnieniu od przytoczonego wyżej jest poprawny. Powyższy daje błędną odpowiedź dla liczb będących trzecią potęgą liczby pierwszej. - bogdans 2011-09-24 08:15

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0