Witam!
Poszukuję algorytmu służącego do wyznaczania najmniejszej liczby całkowitej c mającej co najmniej b dzielników z czego każdy jest nie większy niż a, czyli dzielniki mogą być z przedziału <1;a>.
Przykład:
a = 3, b = 3 -------> c = 6
a = 200, b = 3 --- > c = 4
Nie musi być to kod.. Ważny jest pomysł niezależnie czy to będzie kod, algorytm czy tylko ogólny opis co należy zrobić.
Z góry dziękuje. Pozdrawiam i życzę udanego weekendu! :)
Zadanie konkursowe??
Nie. Zadanie na infe.
Jeśli nie wierzysz to poczekaj do końca konkursu bo zadanie potrzebuje zrobić na czwartek.
przecież to jest banalnie proste, bierzesz kolejne liczby od 1 do min(a,b) i szukasz dla nich najmniejszych wspólnych wielokrotności.
Noo właśnie nie bardzo gdyż min(4,3)=3 a NWW liczb 1, 2 i 3 to 6.
Liczba 6 spełnia założenie gdyż ma minimum 3 dzielniki mniejsze lub równe 4 {1,2,3}.
Natomiast liczba 4 również spełnia założenie gdyż ma 3 dzielniki mniejsze lub równe 4 {1,2,4}
Program ma natomiast zwrócić najmniejszą liczbę..
Więc jednak nie jest to aż takie banalne :)
Rozkminiałem przedstawiać liczbę jako iloczyn potęg kolejnych liczb pierwszych, wtedy:
4 = 2^2
6 = 2 * 3
i na bazie tego szukać algorytmu jednak zagubiłem się w myślach :p
A może jest jakieś prostsze rozwiązanie?