Najmniejsza liczba dodatnia podzielna przez numery 1-20.

0

Zabrałem się za kolejny programik i znów komplikacje :)
Musze znaleźć najmniejszą liczbę dodatnią całkowitą, która będzie się dzielić przez 1, 2, 3, ..., 20.

public class ProjectEuler5 {
    public static void main(String[] args) {
        boolean bool = true;
        int liczba = 1;
        while (bool) {
            int zm = 0;
            for (int i = 11; i <= 20; i++) {
                if (liczba % i == 0) {
                    zm++;
                }
                else
                    continue;
            }
            if (zm == 20) {
                System.out.print(liczba);
                bool = false;
            }
            else
                liczba++;
        }
    }
}

Niby błędów nie ma i jak dodam wypisywanie aktualnie sprawdzanej liczby i maksymalnego zm to coś tam mieli. Jednak zrezygnowałem po 10 minutach mielenia, jak mi program doszedł do liczby 17.218.491 :) Maksymalne zm było 19, a więc już pewnie nie dużo zostało. Ale tak czy siak, coś musi być nie halo, bo pewnie Wy jesteście w stanie zrobić to w 1 sekundę :)

Na początku sprawdzałem od 1 do 20, jednak przemyślałem to i tak na prawdę wystarczy sprawdzić (tak mi się wydaje) jedynie liczby od 11 do 20.
Jeżeli jakaś liczba dzieli się przed 20 to będzie się dzielić też przez 2,4,5,10, jeśli przez 18 to również przez 3,6,9, 16 i 14 to 8 i 7. No i jak wiadomo każda liczba dzieli się przez 1. Przez to wyeliminowałem liczby 1-10 i na pewno skróciłem czas obliczeń, ale nadal są to minuty...

Jak ktoś ma pomysł to niech coś podpowie, tylko bez gotowców i kodów :) Co robię nie tak, że czas obliczeniowy jest tak tragiczny.

0

Nie wiem czy Ci to pomoże, ale nie powinieneś sprawdzać tylko liczby parzystych?
wiec zamiast
liczba++;
daj
liczba += 2
i
int liczba = 2;
chociaż tutaj chyba można było by zacząć od większej liczby niż 1 lub 2?

0

wybaczcie, że tak post pod postem ale czy tutaj
int zm = 0;
nie powinno być
int zm = 11;
?

0

Sprawdzanie liczb parzystych to chyba bardzo dobra podpowiedź tylko czy wystarczy.
Też tak myślałem aby zacząć od jakiejś większej liczby niż 1 sprawdzanie, ale nie miałem pojęcia od jakiej. Szukana liczba jest większa niż 17 mln, a więc te kilkadziesiąt czy kilkaset na początku nie robi różnicy.

0

Powiedz mi czy ta zmienna zm jest tutaj potrzebna? Wydaje mi się (jeżeli dobrze zrozumiałem kod) ze wystarczyła by zmienna i do tego. Ale wymagało by to przerobienia pętli. A co do wartości początkowej to nie mam pojęcia ;/ ale sadze ze to mogło by również troszeczkę przyspieszyć program (podając większą wartość)

0

Co do zmiennej zm, abcsd. Gdyby nie wydawało mi się, ze jest potrzebna to pewnie bym jej stworzył. Pomyśle nad zamianą na i, ale na razie tego nie widzę (na szybkiego).

Jadeszek, właśnie czytam wiki. Algorytm ogólny przedstawia wzór:
user image
Skoro największy wspólny dzielnik tych liczb wynosi 1, to wychodzi z tego, że wynikiem jest 20! (silnia z 20).

To była moja pierwsza myśl po przeczytaniu treści zadania, ale liczba jest tak wielka, że ten pomysł od razu odrzuciłem. Poza tym, zadanie dosyć głupie by było. Chyba, że się mylę odnośnie NWD lub źle odczytuje wzór.

0

Sorry za drobną uwagę nie na temat, ale cała zabawa z ProjectEuler polega na tym że każdy rozwiązuje zadania samodzielnie...
Swojego kodu Ci nie podam bo jest w Haskellu (dobra, i tak bym nie podał), ale mimo że był prawie-brute-force, wykonywał się w chwilę.

A, btw mój program zajmował jedną linijkę kodu ;] (w sumie 25 znaków - sorry, nie mogłem się powstrzymać przed próżnym pochwaleniem się).

Tak czy inaczej:

a = 1
b = NWW(a, 2)
c = NWW(b, 3)
d = NWW(c, 4)
e = NWW(d, 5)
f = NWW(e, 6)
g = NWW(f, 7)
h = NWW(g, 8)
i = NWW(h, 9)
j = NWW(i, 10)
k = NWW(j, 11)
l = NWW(k, 12)
m = NWW(l, 13)
n = NWW(m, 14)
o = NWW(n, 15)
p = NWW(o, 16)
q = NWW(p, 17)
r = NWW(q, 18)
s = NWW(r, 19)
t = NWW(s, 20)
print "wynik:", t
0

Uczę się Javy a zadania robię dla siebie a nie dla jakiegoś rankingu. Nie widzę nic złego w tym, że szukam podpowiedzi u osób, które umieją więcej ode mnie. Możesz przejrzeć moje posty na forum. Nigdy nie proszę o gotowca, wręcz przeciwnie. Piszę aby takowych mi nie wklejano, tylko podpowiedziano co robię źle i naprowadzono na poprawny kierunek. Tym bardziej, że zawsze mam swój kod napisany, czasem lepiej, czasem gorzej, ale nigdy nie przychodzę po pomoc przed rozpoczęciem pisania, a po długim czasie spędzonym przy zadaniu.
Dziś już pasuje. Przerobie sobie na kartce to co napisałeś, bo wcześniej nie zrozumiałem jednak do końca metody wyliczania tego. Jutro spróbuje to przelać do Javy.
Dzięki.

0

ta liczba to [jest sprzeczne z regulaminem ProjectEuler]

public class k {public static void main(String[] args) { int zmienna = 20; while(true){for (int i = 1 ; i <= 20 ; i++ ){if (zmienna % i != 0){break;}if (i == 20){System.out.print("jest to liczba: " + zmienna); }}zmienna++;}}}

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