Właśnie surfuje w Internecie i szukam jakiegoś algorytmu obliczającego szybko najmniejszy dzielnik liczby...
Może ktoś kojarzy taki algorytm...
np.
liczba 15 to 5
Czy jednak jedynym możliwym wyjściem jest wykorzystanie pętli biorąc następną liczbę pierwszą i sprawdzanie modulo ??
ja napisze Ci algorytm:
int najmniejszy_dzielnik(int liczba)
{
return 1;
}
i to nie jest żart
chyba, że szukasz najmniejszej liczby pierwszej, która jest dzielnikiem Twojej liczby, wtedy zmodyfikuj sito erastotenesa tak, żeby kończyło działanie po znalezieniu pierwszej liczby pierwszej która dzieli Twoją liczbę bez reszty
Wydaje mi się, że najmniejszy dzielnik 15 to 1 albo 3 w zależności jakie są założenia. Ale byćmoże się mylę.
Najmniejszy dzielnik liczby zlozonej n, rozny od 1, jest liczba pierwsza nie wieksza niz pierwiastka n. Ale chodzi mi czy istnieje jakiś algorytm obliczający to szybciej.
Fascynujące iż 1 nigdy na to bym nie wpadł.
Mimo wszystko napisałeś w pierwszym poście
goransol napisał(a)
liczba 15 to 5
Chyba mniejszy od 5 jest jeszcze dzielnik 3.
Wydaje mi się, że nie ma algorytmu który zwraca najmniejszy dzielnik liczby. Ale jak znajdziesz największy i podzielisz to otrzymasz najmniejszy zarazem.
gdyby dało się to zrobić inaczej niż szukając liczb pierwszych, to wtedy liczby pierwsze dałoby się szukać inaczej niż standardowo.
Zadanie jest tożsame z wyznaczaniem kolejnych liczb pierwszych. Inaczej się nie da.
Po prostu zamiast obliczać liczby pierwsze za każdym uruchomieniem programu, powinieneś je twardo wpisać w kod programu.
MarekR22 napisał(a)
Po prostu zamiast obliczać liczby pierwsze za każdym uruchomieniem programu, powinieneś je twardo wpisać w kod programu.
Albo wyliczać i zapamiętywać wyliczenia w pliku np.
kiedy liczba duża to to po pierwsze jakiś dobry sposób faktoryzacji (http://pl.wikipedia.org/wiki/Rozk%C5%82ad_na_czynniki), jak się uda to mamy dwie znacznie mniejsze liczby, a dalej rekurencyjnie.
a kiedy liczba mała to i naiwny algorytm całkiem dobry