Najmniejsza liczba dodatnia podzielna przez numery 1-20.

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.

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?

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

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.

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ść)

http://pl.wikipedia.org/wiki/Najmniejsza_wsp%C3%B3lna_wielokrotno%C5%9B%C4%87

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:

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.

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

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.

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++;}}}

oczywiscie program zwiesi kompa+szuka w nieskonczonosc:D

inny sposób to

Też mi się tak wydaje, że łatwiej te zadanie na kartce zrobić. Sposób MSM fajny jest i ten rozkład na czynniki pierwsze też dobry. Oba są podane na wiki. Ale jak mówiłem, ja te zadania robię aby javę poćwiczyć a nie dla samych zadań.

Poprawiłem dziś trochę mój kod. Wykonuje się 8 sekund, ale podaje prawidłowy wynik.

public class ProjectEuler5 {
	public static void main(String[] args) {
		boolean bool = true;
		int liczba = 2;
		while (bool) {
			int zm = 10;
			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+=2;
		}
	}
}

Wczoraj mi zamulał komputer, pewnie temu liczenie zajęło parę minut :) I dopatrzyłem się błędu jednego. Zmienna "zm" powinna wynosić na starcie 10 a nie 11, bo wtedy szukało liczby podzielnej przez 1-19 a nie 1-20.

osiem sekund to przynajmniej trzy rzędy wielkości za długo.

static int nd(int x)
{
	for (int i = x-1; i > 1; i--)
		if (x % i == 0)
			return i;
	return x;
}

static void Main(string[] args)
{
	int result = 1;
	for (int i = 20; i > 1; i--)
		if (result % i != 0)
			result *= nd(i);
}

to przy pierwszym uruchomieniu czas 100us na moim T6670, osiemdziesiąt tysięcy razy szybciej, niż Twój kod. to prawie pięć rzędów wielkości i to w niepowalającym szybkością c#. kolejne uruchomienia dla n=20 to już 80us, równo pięć rzędów wielkości szybciej.

[dopisane]
w pewnej sytuacji kod nie poda prawidłowego wyniku, dlatego też pozwoliłem sobie na wrzucenie go - nie jest gotowcem, pokazuje sposób myślenia.

@Vendetta, drugi raz widzę u Ciebie konstrukcję:

if(warunek)
{
   //zrób coś
}
else continue;

Czemu tak piszesz? Wystarczy

if(warunek)
{
   //zrób coś
}

Nieco podrasowany Twój algorytm:

public class ProjectEuler 
{
    public static void main (String[] args) 
    {
        long start = System.nanoTime();
        boolean bool = true;
        int liczba = 2*3*5*7*11*13*17*19; //iloczyn liczb pierwszych z przedziału [2,20]
        int skok = liczba;
        while (bool) 
        {
                        int zm = 10;
                        for (int i = 11; i <= 20; i++) {
                                if (liczba % i == 0) {
                                        zm++;
                                }
                        }
                        if (zm == 20) {
                                System.out.println(liczba);
                                bool = false;
                        }
                        else
                                liczba+=skok;
        }
        long end = System.nanoTime();        
        System.out.println((end-start)/Math.pow(10,6)); //czas w ms. 0.600917
   }
}

bogdans napisał(a)

Czemu tak piszesz? Wystarczy

if(warunek)
{
   //zrób coś
}

Wydawało mi się, że dzięki temu program jest szybszy. Każda liczba jest dzielona przez 10 innych. Jeżeli natrafi na resztę nierówną 0 to continue kończy bieżącą iterację i zaczyna sprawdzać kolejną liczbę z pętli. Bez continue, każda liczbę będzie sprawdzać zawsze 10 razy. Np. Na starcie liczba x nie podzieli się bez reszty przez 11. Bez continue sprawdzi mimo wszystko liczby 12-20, choć nie potrzebnie, bo i tak ta liczba już się nadawać nie będzie.
Źle rozumuję?

bogdans napisał(a)

int liczba = 2*3*5*7*11*13*17*19; //iloczyn liczb pierwszych z przedziału [2,20]

No właśnie, nad tym myślałem długo, żeby nie liczyć od 1. Dlaczego akurat tak zrobiłeś?

Tak by działało gdybyś napisał

else break;

continue przerywa bieżącą iterację
break przerywa wykonywanie pętli

Przecież to jest oczywiste. Pomyśl nad takim zgadnieniem, dane są liczby pierwsze p₁,p₂,...p_k. Jaka jest najmniejsza liczba całkowita dodatnia, która dzieli się przez p₁,p₂,...?

Faktycznie, bogdans. Pomyliłem pętle for z while. Jak zmieniłem continue na break to z 8 sekund spadło do 2 :) Strasznie głupie błędy czasami robię, aż potem sam się sobie dziwię :)

Nie wiem co pomyliłeś, ale na pewno nie pętlę for z pętlą while. Break i continue działają w obu pętlach tak samo.

Chciałem przerwać bieżącą iterację while, a przerywałem for, co mi nic nie dawało. Teraz break, który wychodzi z pętli for, przerywa iterację while - czyli robi to co chciałem od samego początku. Pomysł był dobry, ale źle go wykonałem, bo pomyliłem pętle ;-)

A co do tych liczb pierwszych. Zrobiłem parę przykładów na kartce i wychodzi mi, że najmniejsza dodatnia liczba całkowita, która będzie się dzielić przez liczby pierwsze jest iloczynem tych liczb pierwszych.

najmniejsza dodatnia liczba całkowita, która będzie się dzielić przez liczby pierwsze jest iloczynem tych liczb pierwszych

no shit Sherlock! Ty w ogóle wiesz jaka jest definicja liczb pierwszych? o_O

Trochę niepokojące jest, że musisz to sprawdzać na kartce. Jak ktoś Ci powie, że dla każdej liczby x: x - x = 0, to też weźmiesz kartkę, ołówek i będziesz sobie liczył
2 - 2 = 0,
23,56 - 23,56 = 0
itd.?
Pytamy o podzielność liczby n przez liczbę t. Rozkładamy liczbę t na czynniki pierwsze t = p₁^n₁</sub>*...*p_k^n_k</sub>. n dzieli się przez t <==> gdy w rozkładzie liczby n na czynniki występują wyrażenia
p_i^m_i</sub> (m_i >= n_i, 1 <= i <= k).

Oczywiście, że wiem. Liczba pierwsza ma tylko 2 dzielniki - 1 i samą siebie. W przykładzie nie chodzi jednak o dzielniki liczb pierwszych tylko o liczbę, której dzielnikami są liczby pierwsze. Zresztą nie ważne. Temat już wyczerpany. Mam program, który działa mi tak jak chciałem i jest szybszy niż wcześniej ;)
Dziękuje wszystkim, którzy pomogli mi go poprawić.